Reachability Preservers: New Extremal Bounds and Approximation Algorithms
From MaRDI portal
Publication:6154193
DOI10.1137/21m1442176OpenAlexW2766479655MaRDI QIDQ6154193
Publication date: 19 March 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1442176
reachabilitygraph algorithmsapproximation algorithmsextremal graph theorypreserversdirected Steiner networkgraph sparsifiers
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- A new proof of the graph removal lemma
- Finding paths and deleting edges in directed acyclic graphs
- The convex hull of the integer points in a large ball
- New pairwise spanners
- An improved construction of progression-free sets
- Approximation algorithms for spanner problems and directed Steiner forest
- A note on distance-preserving graph sparsification
- Dual Failure Resilient BFS Structure
- Design networks with bounded pairwise distance
- Preserving Terminal Distances Using Minors
- Sparse Fault-Tolerant BFS Trees
- Dial a Ride from k -forest
- On Pairwise Spanners
- Vertex Sparsification in Trees
- Set connectivity problems in undirected graphs and the directed steiner network problem
- Sparse Sourcewise and Pairwise Distance Preservers
- Small Stretch Pairwise Spanners and Approximate $D$-Preservers
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Lower-Stretch Spanning Trees
- Approximating Low-Stretch Spanners
- Error Amplification for Pairwise Spanner Lower Bounds
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Steiner Point Removal --- Distant Terminals Don't (Really) Bother
- Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm
- The 4/3 Additive Spanner Exponent Is Tight
- Compact roundtrip routing in directed networks
- Transitive-Closure Spanners
- Transitive-Closure Spanners: A Survey
- Approximation Algorithms for Directed Steiner Problems
- Roundtrip spanners and roundtrip routing in directed graphs
- Better Distance Preservers and Additive Spanners
- Distance-Preserving Subgraphs of Interval Graphs
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- Refined Vertex Sparsifiers of Planar Graphs
- Improved Guarantees for Vertex Sparsification in Planar Graphs
- Fault tolerant subgraph for single source reachability: generic and optimal
- Sparse Distance Preservers and Additive Spanners
- Depth-First Search and Linear Graph Algorithms
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- New Results on Linear Size Distance Preservers
- Vertex Sparsifiers: New Results from Old Techniques
