Distance-Preserving Graph Contractions
From MaRDI portal
Publication:4993321
DOI10.4230/LIPIcs.ITCS.2018.51zbMath1462.68133OpenAlexW2964311045MaRDI QIDQ4993321
Frieder Smolny, Max Klimm, Yann Disser, Karl Däubel, Torsten Mütze, Aaron Bernstein
Publication date: 15 June 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8342/pdf/LIPIcs-ITCS-2018-51.pdf/
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Retracting Graphs to Cycles ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Subgraphs of Interval Graphs
Uses Software
Cites Work
- Unnamed Item
- 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
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Complexity of network synchronization
- Graph spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Graph Partitioning and Graph Clustering
- Additive graph spanners
- The 4/3 additive spanner exponent is tight
- Deterministic decremental single source shortest paths: beyond the o(mn) bound
This page was built for publication: Distance-Preserving Graph Contractions
