Preserving distances in very faulty graphs

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

Fabrizio Grandoni, Greg Bodwin, 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 (10)

• Graph spanners: a tutorial review
• Efficient Oracles and Routing Schemes for Replacement Paths
• Blackout-tolerant temporal spanners
• New Results on Linear Size Distance Preservers
• Sparse Weight Tolerant Subgraph for Single Source Shortest Path
• Title not available (Why is that?)
• 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

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)