Algorithms for Multiterminal Cuts

DOI10.1007/978-3-540-79709-8_32zbMath1142.68462MaRDI QIDQ3503649

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

Multicut; Graph Algorithm; Fixed Parameter Tractability; Multiterminal Cut

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

FPT algorithms for path-transversal and cycle-transversal problems, Simple and improved parameterized algorithms for multiterminal cuts, Constant ratio fixed-parameter approximation of the edge multicut problem, Important Separators and Parameterized Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• An improved approximation algorithm of MULTIWAY CUT.
• A Simple Algorithm for the Planar Multiway Cut Problem
• A 2-Approximation Algorithm for the Directed Multiway Cut Problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Finding small balanced separators
• Beyond the flow decomposition barrier
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs