Faster swap edge computation in minimum diameter spanning trees

DOI10.1007/s00453-010-9448-3zbMath1397.05190MaRDI QIDQ2428664

Beat Gfeller

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/69265

zbMATH Keywords

fault tolerance; graph algorithms; transient edge failures; minimum diameter spanning tree

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

68M10: Network design and communication in computer systems

05C85: Graph algorithms (graph-theoretic aspects)

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

A faster computation of all the best swap edges of a shortest paths tree

Cites Work

• Computing all the best swap edges distributively
• Finding the most vital node of a shortest path.
• Swapping a failing edge of a single source shortest paths tree is good and fast
• On computing a longest path in a tree
• Single backup table schemes for shortest-path routing
• Nearly linear time minimum spanning tree maintenance for transient node failures
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The swap edges of a multiple-sources routing tree
• Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree