Flow-Cut Gaps and Face Covers in Planar Graphs

DOI10.1137/1.9781611975482.33zbMath1434.05124arXiv1811.02685OpenAlexW2899946382MaRDI QIDQ5236214

Havana Rika, James R. Lee, Robert Krauthgamer

Publication date: 15 October 2019

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

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

zbMATH Keywords

sparsest cutmaximum concurrent multi-flow

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Flows in graphs (05C21)

Related Items (2)

Unnamed Item ⋮ Refined Vertex Sparsifiers of Planar Graphs

This page was built for publication: Flow-Cut Gaps and Face Covers in Planar Graphs