Extensions and limits to vertex sparsification

DOI10.1145/1806689.1806698MaRDI QIDQ2875131zbMATH OpenOpenAlexFDO

Authors Ankur Moitra, F. Thomson 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

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

Recommendations

• Vertex sparsifiers: new results from old techniques
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsification and oblivious reductions
• On vertex sparsifiers with Steiner nodes
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size

Cited in

(27)

• On mimicking networks representing minimum terminal cuts
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Routing in undirected graphs with constant congestion
• Improved guarantees for tree cut sparsifiers
• Vertex sparsification in trees
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• Separator-Based Sparsification II: Edge and Vertex Connectivity
• Note: Small integral flows need only sparse networks
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
• Vertex sparsification and oblivious reductions
• On vertex sparsifiers with Steiner nodes
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Vertex sparsifiers: new results from old techniques
• Vertex Sparsifiers: New Results from Old Techniques
• Some aspects of graph sparsification in theory and practice
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
• Scattering and sparse partitions, and their applications
• Lower bounds on 0-extension with Steiner nodes
• Scattering and sparse partitions, and their applications
• Additive sparsification of CSPs
• Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
• Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875131)