Distance-Preserving Graph Contractions
From MaRDI portal
Publication:5233754
DOI10.1137/18M1169382zbMath1430.68177arXiv1705.04544OpenAlexW2971548643WikidataQ127320834 ScholiaQ127320834MaRDI QIDQ5233754
Yann Disser, Frieder Smolny, Torsten Mütze, Aaron Bernstein, Karl Däubel, Max Klimm
Publication date: 6 September 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.04544
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
The complexity of contracting bipartite graphs into small cycles ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Distance-Preserving Graph Contractions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On sparse spanners of weighted graphs
- Preserving Terminal Distances Using Minors
- Sparse Sourcewise and Pairwise Distance Preservers
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Complexity of network synchronization
- Graph spanners
- Cyclic Scheduling via Integer Programs with Circular Ones
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Generating Sparse 2-Spanners
- Better Distance Preservers and Additive Spanners
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- Linear Size Distance Preservers
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Graph Partitioning and Graph Clustering
- Sampling random spanning trees faster than matrix multiplication
- Distance-Preserving Graph Contractions
- Reducibility among Combinatorial Problems
- Kron Reduction of Graphs With Applications to Electrical Networks
- Distance-Preserving Graph Contractions
- Additive graph spanners
- Towards Resistance Sparsifiers
- The 4/3 additive spanner exponent is tight
- Deterministic decremental single source shortest paths: beyond the o(mn) bound
- Computing and Combinatorics
- On the hardness of approximating spanners
This page was built for publication: Distance-Preserving Graph Contractions
