Vertex fault tolerant additive spanners

DOI10.1007/s00446-015-0252-9zbMath1425.68042arXiv1408.0409OpenAlexW2952064537MaRDI QIDQ1689749

Merav Parter

Publication date: 17 January 2018

Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

spannersreplacement pathsadditive stretch

Mathematics Subject Classification ID

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

Related Items (12)

Improved Purely Additive Fault-Tolerant Spanners ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ Graph spanners: a tutorial review ⋮ Fault-tolerant approximate shortest-path trees ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Bounded degree spanners of the hypercube ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Output sensitive fault tolerant maximum matching

Cites Work

• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• Sparse Fault-Tolerant BFS Trees
• Fault-Tolerant Approximate Shortest-Path Trees
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Fault-tolerant spanners
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• New Pairwise Spanners
• On Pairwise Spanners
• Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• All-Pairs Almost Shortest Paths
• A nearly optimal oracle for avoiding failed vertices and edges
• Fault-tolerant spanners for general graphs
• Fault Tolerant Additive Spanners
• Small Stretch Pairwise Spanners
• Low Distortion Spanners
• New Additive Spanners

This page was built for publication: Vertex fault tolerant additive spanners