Preserving distances in very faulty graphs

DOI10.4230/LIPICS.ICALP.2017.73zbMATH Open1441.68166arXiv1703.10293MaRDI QIDQ5111404FDOQ5111404

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

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

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)

Cited In (12)

• Graph spanners: a tutorial review
• Blackout-tolerant temporal spanners
• New results on linear size distance preservers
• Sparse weight tolerant subgraph for single source shortest path
• Restorable Shortest Path Tiebreaking for Edge-Faulty 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)