Sparse Weight Tolerant Subgraph for Single Source Shortest Path

DOI10.4230/LIPIcs.SWAT.2018.15zbMath1477.05177arXiv1707.04867OpenAlexW2805276497MaRDI QIDQ5116479

Diptarka Chakraborty, Debarati Das

Publication date: 25 August 2020

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

zbMATH Keywords

shortest pathgraph algorithmfault tolerantdistance preserver

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex fault tolerant additive spanners
• Fault-tolerant geometric spanners
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Dual Failure Resilient BFS Structure
• Sparse Fault-Tolerant BFS Trees
• Speeding Up Dynamic Shortest-Path Algorithms
• Fault-Tolerant Approximate Shortest-Path Trees
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Fault-tolerant spanners
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Improved Purely Additive Fault-Tolerant Spanners
• Oracles for Distances Avoiding a Failed Node or Link
• Additive Spanners in Nearly Quadratic Time
• A fast algorithm for finding dominators in a flowgraph
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Multiple-edge-fault-tolerant approximate shortest-path trees
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Multiple Source Dual Fault Tolerant BFS Trees
• A nearly optimal oracle for avoiding failed vertices and edges
• Fault-tolerant spanners for general graphs
• The 4/3 additive spanner exponent is tight
• Fault tolerant subgraph for single source reachability: generic and optimal
• Fault Tolerant Approximate BFS Structures

This page was built for publication: Sparse Weight Tolerant Subgraph for Single Source Shortest Path