Distance-preserving graph contractions

Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny

Type: Preprint

Publication Date: 2017-05-12

Citations: 1

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Distance-preserving graph contractions	2017	Aaron Bernstein Karl Däubel Yann Disser Max Klimm Torsten Mütze Frieder Smolny
+ PDF Chat	Distance-Preserving Graph Contractions	2019	Aaron Bernstein Karl Däubel Yann Disser Max Klimm Torsten Mütze Frieder Smolny
+ PDF Chat	Distance-Preserving Graph Compression Techniques	2024	Amirali Madani Anil Maheshwari
+ PDF Chat	A note on distance-preserving graph sparsification	2021	Greg Bodwin
+	Distance-Preserving Graph Compression Techniques	2023	Amirali Madani Anil Maheshwari
+	Path-contractions, edge deletions and connectivity preservation	2017	Gregory Gutin M. S. Ramanujan Felix Reidl Magnus Wahlström
+	Path-contractions, edge deletions and connectivity preservation	2017	Gregory Gutin M. S. Ramanujan Felix Reidl Magnus Wahlström
+	Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections	2019	Gramoz Goranci
+	Quasi-Isometric Graph Simplifications	2021	Khí-Uí Soo Bakhadyr Khoussainov Simone Linz
+	Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds	2016	Yun Kuen Cheung Gramoz Goranci Monika Henzinger
+	Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds	2016	Yun Kuen Cheung Gramoz Goranci Monika Henzinger
+	Inapproximability of Additive Weak Contraction under SSEH and Strong UGC	2019	Siddhartha Jain
+	$O(1)$ Steiner Point Removal in Series-Parallel Graphs	2021	D Ellis Hershkowitz Jason Li
+	Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs	2021	Zhiyang He Jason Li Magnus Wahlström
+ PDF Chat	Preserving Terminal Distances Using Minors	2014	Robert Krauthgamer Huy L. Nguyễn Tamar Zondiner
+	Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs	2020	Zhiyang He Jason Li Magnus Wahlström
+	Vertex Sparsification for Edge Connectivity	2020	Parinya Chalermsook Syamantak Das Bundit Laekhanukit Yunbum Kook Yang P. Liu Richard Peng Mark Sellke Daniel Vaz
+	Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class	2018	Erik D. Demaine Timothy D. Goodrich Kyle Kloster Brian Lavallee Quanquan C. Liu Blair D. Sullivan Ali Vakilian Andrew van der Poel
+	Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class	2018	Erik D. Demaine Timothy D. Goodrich Kyle Kloster Brian Lavallee Quanquan C. Liu Blair D. Sullivan Ali Vakilian Andrew van der Poel
+	Generalized Metric Repair on Graphs	2019	Chenglin Fan Anna C. Gilbert Benjamin Raichel Rishi Sonthalia Gregory Van Buskirk

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Minimizing Branching Vertices in Distance-Preserving Subgraphs	2019	Kshitij Gajjar Jaikumar Radhakrishnan

Works Cited by This (8)

Action	Title	Year	Authors
+	Extremal problems in graph theory	1997	Christopher M. Hartman
+	Extremal graphs with no C4's, C6's, or C10's	1991	Rephael Wenger
+ PDF Chat	Preserving Terminal Distances Using Minors	2014	Robert Krauthgamer Huy L. Nguyễn Tamar Zondiner
+	The 4/3 additive spanner exponent is tight	2016	Amir Abboud Greg Bodwin
+	Sampling random spanning trees faster than matrix multiplication	2017	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva
+ PDF Chat	Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions	2018	Timothy Chu Yu Gao Richard Peng Sushant Sachdeva Saurabh Sawlani Junxing Wang
+ PDF Chat	Kron Reduction of Graphs With Applications to Electrical Networks	2013	Florian Dörfler Francesco Bullo
+ PDF Chat	Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple	2016	Rasmus Kyng Sushant Sachdeva