On mimicking networks representing minimum terminal cuts

DOI10.1016/j.ipl.2014.02.011zbMath1284.05295arXiv1207.6371OpenAlexW2068727899MaRDI QIDQ2446595

Arindam Khan, Prasad Raghavendra

Publication date: 17 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial problemsanalysis of algorithmsgraph algorithmsapproximation algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Tight Bounds for Gomory-Hu-like Cut Counting ⋮ Vertex Sparsification in Trees ⋮ 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 ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs

Cites Work

• Unnamed Item
• Computing mimicking networks
• Extensions and limits to vertex sparsification
• Flows in One-Crossing-Minor-Free Graphs
• Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
• All-Pairs Min-Cut in Sparse Networks
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• On vertex sparsifiers with Steiner nodes
• Mimicking Networks and Succinct Representations of Terminal Cuts