Extensions and limits to vertex sparsification
From MaRDI portal
Publication:2875131
DOI10.1145/1806689.1806698zbMath1293.05149OpenAlexW2012776084MaRDI QIDQ2875131
Ankur Moitra, Frank Thompson Leighton
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806698
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)
Related Items
Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ Vertex Sparsification in Trees ⋮ On mimicking networks representing minimum terminal cuts ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ 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 ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points