Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

DOI10.4230/LIPIcs.ICALP.2016.131zbMath1388.68214arXiv1604.08342MaRDI QIDQ4598273

Yun Kuen Cheung, Gramoz Goranci, Monika R. Henzinger

Publication date: 19 December 2017

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

zbMATH Keywords

graph minormetric embeddinggraph compressiondistance approximating minorvertex sparsification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83)

Related Items

Reachability Preservers: New Extremal Bounds and Approximation Algorithms, Unnamed Item, Vertex Sparsification in Trees, Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm, Refined Vertex Sparsifiers of Planar Graphs, Improved Guarantees for Vertex Sparsification in Planar Graphs, Unnamed Item, Distance-Preserving Graph Contractions, Distance-Preserving Subgraphs of Interval Graphs, Distance-Preserving Graph Contractions