Algorithms for Multiterminal Cuts

DOI10.1007/978-3-540-79709-8_32zbMath1142.68462OpenAlexW1519134344MaRDI 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

MulticutGraph AlgorithmFixed Parameter TractabilityMultiterminal Cut

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms for Multiterminal Cuts