Approximating the k-multicut problem

DOI10.1145/1109557.1109625zbMath1192.90170OpenAlexW4247051268MaRDI QIDQ3581503

Mohit Singh, Viswanath Nagarajan, Daniel Golovin

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109625

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (16)

Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Partial multicuts in trees ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ A unified approach to approximating partial covering problems ⋮ Unnamed Item ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ The checkpoint problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Approximation Algorithms for k-Hurdle Problems ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Approximation algorithms for the partition vertex cover problem ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ On the parameterized complexity of separating certain sources from the target

This page was built for publication: Approximating the k-multicut problem