Towards (1 + ∊)-Approximate Flow Sparsifiers

DOI10.1137/1.9781611973402.20zbMath1422.68280arXiv1310.3252OpenAlexW4248360301MaRDI QIDQ5383979

Anupam Gupta, Robert Krauthgamer, Alexandr Andoni

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (7)

Temporal flows in temporal networks ⋮ 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 ⋮ An exponential lower bound for cut sparsifiers in planar graphs

This page was built for publication: Towards (1 + ∊)-Approximate Flow Sparsifiers