Multipath Spanners via Fault-Tolerant Spanners

DOI10.1007/978-3-642-34862-4_8zbMath1385.68025OpenAlexW102070137MaRDI QIDQ4916037

Shiri Chechik, Quentin Godfroy, David Peleg

Publication date: 19 April 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-34862-4_8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On sparse spanners of weighted graphs
• Spanners and message distribution in networks.
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Compact Routing with Minimum Stretch
• Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
• Fault-tolerant spanners
• Approximate distance oracles
• Multipath Spanners
• Graph spanners
• An Optimal Synchronizer for the Hypercube
• Compact roundtrip routing in directed networks
• Roundtrip spanners and roundtrip routing in directed graphs
• Fault-tolerant spanners for general graphs
• Deterministic distributed vertex coloring in polylogarithmic time
• Average size of unstretched Remote-Spanners
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Low Distortion Spanners
• Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
• Computing almost shortest paths
• Performance of multipath routing for on-demand protocols in mobile ad hoc networks