An approximation algorithm for the generalized \(k\)-multicut problem
From MaRDI portal
Publication:423940
DOI10.1016/j.dam.2012.01.016zbMath1255.68312OpenAlexW2088728264MaRDI QIDQ423940
Daming Zhu, Junfeng Luan, Peng Zhang
Publication date: 30 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.01.016
Related Items (4)
An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ On the generalized multiway cut in trees problem ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
Cites Work
- Primal-dual approximation algorithms for integral flow and multicut in trees
- A note on the prize collecting traveling salesman problem
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- An improved approximation algorithm of MULTIWAY CUT.
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Detecting high log-densities
- Multiway cut and integer flow problems in trees
- Dial a Ride from k-Forest
- Approximating the k-multicut problem
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- On the multiway cut polyhedron
- The Complexity of Multiterminal Cuts
- A General Approximation Technique for Constrained Forest Problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Algorithm Theory - SWAT 2004
- Approximating Generalized Multicut on Trees
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation and Online Algorithms
- The dense \(k\)-subgraph problem
- Unnamed Item
This page was built for publication: An approximation algorithm for the generalized \(k\)-multicut problem
