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

Fixed Parameter TractabilityGraph AlgorithmMulticutMultiterminal Cut

Mathematics Subject Classification ID

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

Recommendations

• Simple and improved parameterized algorithms for multiterminal cuts
• The Complexity of Multiterminal Cuts
• The planar multiterminal cut problem
• scientific article; zbMATH DE number 176254
• An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem

Cites work

• 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
• 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?)
• 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

(19)

• Multiterminal flows and cuts
• Isolation branching: a branch and bound algorithm for the k-terminal cut problem
• Faster exact algorithms for some terminal set problems
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• An algorithm for computing maximum solution bases
• An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem
• Towards Algorithmic Cut-Introduction
• Algorithms Solving the Matching Cut Problem
• Important separators and parameterized algorithms
• Multiple Cuts in Separating Plane Algorithms
• Algorithms for 2-Route Cut Problems
• Multi-terminal cuts in generalized tree networks
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• The Complexity of Multiterminal Cuts
• FPT algorithms for path-transversal and cycle-transversal problems
• Experimental and Efficient 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

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)