Improved Purely Additive Fault-Tolerant Spanners

DOI10.1007/978-3-662-48350-3_15zbMath1465.68205arXiv1507.00505OpenAlexW1906469382MaRDI QIDQ3452780

Fabrizio Grandoni, Davide Bilò, Stefano Leucci, Luciano Gualà, Guido Proietti

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

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)

Related Items (12)

Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Graph spanners: a tutorial review ⋮ Fault-tolerant approximate shortest-path trees ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Output sensitive fault tolerant maximum matching ⋮ Unnamed Item

Cites Work

• On resilient graph spanners
• On sparse spanners of weighted graphs
• Vertex fault tolerant additive spanners
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Sparse Fault-Tolerant BFS Trees
• Fault-Tolerant Approximate Shortest-Path Trees
• Fault-tolerant spanners
• On Pairwise Spanners
• Additive spanners and (α, β)-spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• f-Sensitivity Distance Oracles and Routing Schemes
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fault-Tolerant Approximate BFS Structures
• A nearly optimal oracle for avoiding failed vertices and edges
• Fault-tolerant spanners for general graphs
• Fault Tolerant Additive Spanners

This page was built for publication: Improved Purely Additive Fault-Tolerant Spanners