Preserving Terminal Distances Using Minors

DOI10.1007/978-3-642-31594-7_50zbMath1271.05092arXiv1202.5675OpenAlexW1521196338MaRDI QIDQ2843284

Tamar Zondiner, Robert Krauthgamer

Publication date: 12 August 2013

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

metric embeddinggraph compressiondistance preserving minordistance-preserving minorvertex-sparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Related Items (12)

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 ⋮ Unnamed Item ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Subgraphs of Interval Graphs ⋮ Distance-Preserving Graph Contractions ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points

This page was built for publication: Preserving Terminal Distances Using Minors