Preserving distances in very faulty graphs

DOI10.4230/LIPICS.ICALP.2017.73MaRDI QIDQ5111404zbMATH OpenFDO

Authors Greg Bodwin, Fabrizio Grandoni, M. Parter, Virginia Vassilevska Williams

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1703.10293

zbMATH Keywords

shortest pathsfault tolerancereplacement paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Fault tolerant spanners for general graphs
• Fault-tolerant spanners for general graphs
• Improved purely additive fault-tolerant spanners
• Fault tolerant additive spanners
• Fault tolerant additive and \((\mu, \alpha)\)-spanners

Cited in

(19)

• Graph spanners: a tutorial review
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Blackout-tolerant temporal spanners
• Restorable shortest path tiebreaking for edge-faulty graphs
• New results on linear size distance preservers
• Fault tolerant max-cut
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• Sparse weight tolerant subgraph for single source shortest path
• Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
• Connectivity labeling in faulty colored graphs
• Efficient oracles and routing schemes for replacement paths
• Generic single edge fault tolerant exact distance oracle
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Distributed constructions of dual-failure fault-tolerant distance preservers
• Maintaining exact distances under multiple edge failures
• An efficient strongly connected components algorithm in the fault tolerant model
• Designing distrance-preserving fault-tolerant topologies

This page was built for publication: Preserving distances in very faulty graphs

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