Algorithms for Multiterminal Cuts

DOI10.1007/978-3-540-79709-8_32MaRDI QIDQ3503649zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_32

zbMATH Keywords

MulticutGraph AlgorithmFixed Parameter TractabilityMultiterminal Cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Simple and improved parameterized algorithms for multiterminal cuts
• The Complexity of Multiterminal Cuts
• The planar multiterminal cut problem
• Publication:4035360
• An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A 2-approximation algorithm for the directed multiway cut problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A simple algorithm for the planar multiway cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• Beyond the flow decomposition barrier
• Finding small balanced separators
• Minimal multicut and maximal integer multiflow: a survey
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs
• Parameterized graph separation problems
• The Complexity of Multiterminal Cuts

Cited in

(18)

• Algorithms Solving the Matching Cut Problem
• FPT algorithms for path-transversal and cycle-transversal problems
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• Isolation branching: a branch and bound algorithm for the k-terminal cut problem
• An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem
• Multiple Cuts in Separating Plane Algorithms
• SOFSEM 2006: Theory and Practice of Computer Science
• Simple and improved parameterized algorithms for multiterminal cuts
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Multiterminal flows and cuts
• Algorithms for 2-Route Cut Problems
• Experimental and Efficient Algorithms
• Multi-terminal cuts in generalized tree networks
• Towards Algorithmic Cut-Introduction
• Important separators and parameterized algorithms
• An algorithm for computing maximum solution bases
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Faster exact algorithms for some terminal set problems

This page was built for publication: Algorithms for Multiterminal Cuts

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