Generalized k-multiway cut problems

DOI10.1007/BF02896389MaRDI QIDQ2504075zbMATH OpenOpenAlexFDO

Authors Cheng Zhao, Jiping Liu, Yuejian Peng

Publication date 22 September 2006

Published in Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02896389

zbMATH Keywords

local search algorithmnear-optimum approximation algorithmsNP-hard problemsrandomized algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• An approximation algorithm for the generalized k-multicut problem
• On the generalized multiway cut in trees problem
• On the generalized multiway cut in trees problem
• The multi-multiway cut problem
• Algorithm Theory - SWAT 2004
• On the \(k\)-cut problem
• Multi-multiway cut problem on graphs of bounded branch width
• scientific article; zbMATH DE number 176254
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.

Cites work

• A new approach to the maximum-flow problem
• Approximation Algorithms for Some Graph Partitioning Problems
• How easy is local search?
• Local search and the local structure of NP-complete problems
• Optimization, approximation, and complexity classes
• Simple Local Search Problems that are Hard to Solve
• Some graph partitioning problems
• The Complexity of Multiterminal Cuts
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(11)

• Approximation algorithms for multi-parameter graph optimization problems
• A generalized \(\alpha\)-cut
• Greedy splitting algorithms for approximating multiway partition problems
• Generalizing the all-pairs min cut problem
• k-cuts: a variation of Gomory mixed integer cuts from the LP tableau
• The generalized good cut equation
• On the multiway cut polyhedron
• An approximation algorithm for the generalized k-multicut problem
• Approximation Algorithms for k-Hurdle Problems
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• A local search approximation algorithm for the multiway cut problem

This page was built for publication: Generalized \(k\)-multiway cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2504075)