Vertex Sparsifiers: New Results from Old Techniques

DOI10.1137/130908440zbMath1302.90234OpenAlexW3100089996MaRDI QIDQ5891880

Robert Krauthgamer, Kunal Talwar, Harald Räcke, Matthias Englert, Anupam Gupta, Inbal Talgam-Cohen

Publication date: 14 November 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130908440

zbMATH Keywords

planar graphsapproximation algorithmsmulticommodity flowgraph minorsmetric decomposition0-extensionsflow sparsifiervertex sparsifier

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Terminal embeddings ⋮ Metric decompositions of path-separable graphs ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Unnamed Item ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ An exponential lower bound for cut sparsifiers in planar graphs