Fault-tolerant spanners for general graphs

DOI10.1145/1536414.1536475zbMath1304.68138OpenAlexW2018956470MaRDI QIDQ5172738

Liam Roditty, Shiri Chechik, Michael Langberg, David Peleg

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536475

zbMATH Keywords

graphsfault-tolerancespanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Signed and weighted graphs (05C22)

Related Items (9)

Improved Purely Additive Fault-Tolerant Spanners ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Vertex fault tolerant additive spanners ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Fault-tolerant approximate shortest-path trees ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners

This page was built for publication: Fault-tolerant spanners for general graphs