Approximating Multicut and the Demand Graph

DOI10.1137/1.9781611974782.54zbMath1410.90232arXiv1607.07200OpenAlexW2953295821MaRDI QIDQ4575793

Vivek Madan, Chandra Chekuri

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

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

Related Items (5)

Global and fixed-terminal cuts in digraphs ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Beating the 2-approximation factor for global bicut

This page was built for publication: Approximating Multicut and the Demand Graph