Faster swap edge computation in minimum diameter spanning trees

DOI10.1007/S00453-010-9448-3MaRDI QIDQ2428664zbMATH OpenOpenAlexFDO

Authors 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

graph algorithmsfault tolerancetransient edge failuresminimum diameter spanning tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10)

Recommendations

• Faster Swap Edge Computation in Minimum Diameter Spanning Trees
• scientific article; zbMATH DE number 1305082
• Maintaining spanning trees of small diameter
• A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
• A Faster Computation of All the Best Swap Edges of a Tree Spanner

Cites work

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

Cited in

(7)

• A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
• Faster Swap Edge Computation in Minimum Diameter Spanning Trees
• Computing Best Swaps in Optimal Tree Spanners
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• An edge-swap heuristic for finding dense spanning trees
• Linear time distributed swap edge algorithms
• A faster computation of all the best swap edges of a shortest paths tree

This page was built for publication: Faster swap edge computation in minimum diameter spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428664)