Fault tolerant additive and (, )-spanners

DOI10.1016/J.TCS.2015.02.036MaRDI QIDQ2344775zbMATH OpenOpenAlexFDO

Authors Gilad Braunschvig, Shiri Chechik, David Peleg, Adam Sealfon

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.036

zbMATH Keywords

additive spannersfault tolerancegraph algorithmsspanners

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Recommendations

• Fault tolerant additive spanners
• Improved purely additive fault-tolerant spanners
• Fault-tolerant spanners for general graphs
• Fault tolerant spanners for general graphs
• Fault-tolerant spanners

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A trade-off between space and efficiency for routing tables
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners in nearly quadratic time
• All-Pairs Almost Shortest Paths
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles
• Automata, Languages and Programming
• Computing graph spanners in small memory: fault-tolerance and streaming
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fault-tolerant geometric spanners
• Fault-tolerant spanners
• Fault-tolerant spanners for general graphs
• scientific article; zbMATH DE number 2185613 (Why is no real title available?)
• scientific article; zbMATH DE number 1775403 (Why is no real title available?)
• Low distortion spanners
• New additive spanners
• On sparse spanners of weighted graphs
• Spanners and emulators with sublinear distance errors
• Spanners and message distribution in networks.

Cited in

(18)

• Graph spanners: a tutorial review
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• Mincut sensitivity data structures for the insertion of an edge
• Self-spanner graphs
• Connectivity oracles for graphs subject to vertex failures
• Improved purely additive fault-tolerant spanners
• Multipath spanners via fault-tolerant spanners
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Preserving distances in very faulty graphs
• Sparse weight tolerant subgraph for single source shortest path
• Fault tolerant additive spanners
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Distributed constructions of dual-failure fault-tolerant distance preservers
• An efficient strongly connected components algorithm in the fault tolerant model
• Deterministic replacement path covering
• Restorable shortest path tiebreaking for edge-faulty graphs
• Bounded degree spanners of the hypercube

This page was built for publication: Fault tolerant additive and \((\mu, \alpha)\)-spanners

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