Extensions and limits to vertex sparsification

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

zbMATH Keywords

multicommodity flowoblivious reductions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Related Items (11)

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

This page was built for publication: Extensions and limits to vertex sparsification