#spanning tree

Radia Perlman

“Portsmouth, Virginia-born computer scientist Radia Perlman to thank for the internet. Perlman developed the algorithm behind the spanning-tree protocol (STP), an innovation that made today’s internet possible.”

Radia Perlman, informatica statunitense, tra le maggiori esperte mondiali di software design e ingegneria informatica, è l’inventrice dello Spanning Tree Protocol (STP) che ha reso più efficiente la rete, ottimizzando il collegamento tra i suoi nodi.

Nominata Inventrice dell’anno 2004 dalla Silicon Valley Intellectual Property Law Association, è stata annoverata tra le 20 persone più influenti nel campo della tecnologia da Data Communications Magazine.

Nata a Portsmouth, in Virginia, il 18 dicembre 1951, da una coppia di ingegneri che lavorava per il Governo, ha vissuto a lungo in New Jersey. Brillante studentessa in scienze e matematica al liceo, dopo il diploma è stata tra le rarissime ragazze a frequentare il MIT (Massachusetts Institute of Technology) dove, nel 1976, si è laureata in Matematica.

Nel 1980, lavorando per Digital Equipment Corp, colosso dei computer, agli albori di internet, ha prodotto l’algoritmo per STP.

Nel 1988 ha conseguito il dottorato in informatica presso il MIT.

Ha lasciato Digital nel 1993 per lavorare per Novell e nel 1997 è entrata in Sun Microsystems, dove si è specializzata nella sicurezza di rete. Nel 2007, le è stato conferito il titolo di Distinguished Engineer. 

Ha insegnato alle Università di Harvard e di Washington. Nel corso della sua carriera ha ottenuto circa 80 brevetti.

È l’autrice di Interconnections: Bridges and Routers e coautrice (assieme a Charlie Kaufman) di Network Security: Private Communication in a Public World, due fra i dieci più importanti testi in materia di networking.

The average distanceof a finite graph is the average of the distances over all unordered pairs of vertices which can be used as a tool in analytic networks where the performance time is proportional to the distance between any two nodes. A minimum average distance spanning tree of is a spanning tree of with minimum average distance. Such a tree is sometimes referred to as a minimum routing cost spanning tree and these are of interest in the design of communication networks. In this chapter, I present an efficient algorithm to compute a minimum average distance spanning tree on trapezoid graphs in time, where is the number of vertices of the graph.

Author(s) Details

Dr. Sukumar Mondal Department of Mathematics, Raja N. L. Khan Women's College (Autonomous), Gope Palace, Paschim Medinipur, 721 102, West Bengal, India.

“VERY simply put Spanning-Tree Protocol (aka STP) blocks one of those links to prevent a loop.  If another of the links goes down then the blocked one is unblocked so you don't lose connectivity.  The real fun part is the different versions and technologies that go with each.  Here is a quick summary of the types for you if you are a crazy like me and would like to have something to throw into Google and read up more on. “

Link: Spanning tree

Choose any finite connected graph, call it G.

If the graph has no cycles, then it is a tree. So, G is its own spanning tree.

Otherwise, there is a cycle. In fact, there must be a finite number of cycles. Choose one of the cycles, and a specific edge in it. Call that edge e.

Make a new graph G1 which is just like G, except it does not contain e.

This process does not disconnect the graph, since any path through e can also go the other way through the cycle e is in.

G1 spans G, since they both have the same vertices, and the edges in G1 are a subset of edges in G.

If G1 still has a cycle, then make G2 in the same way G1 was made.

Since there are a finite number of cycles to break up, this process must terminate in a tree.