Simple and improved parameterized algorithms for multiterminal cuts

DOI10.1007/s00224-009-9215-5zbMath1213.68472OpenAlexW2005309613MaRDI QIDQ987378

Mingyu Xiao

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9215-5

zbMATH Keywords

graph algorithmparameterized algorithmmulticutmultiterminal cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the complexity of barrier resilience for fat regions and bounded ply ⋮ Linear kernels for separating a graph into components of bounded size ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Clique Cover and Graph Separation ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ On the generalized multiway cut in trees problem ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ How to Cut a Graph into Many Pieces ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Slightly Superexponential Parameterized Problems ⋮ Unnamed Item ⋮ An FPT algorithm for edge subset feedback edge set ⋮ On Computing the Maximum Parsimony Score of a Phylogenetic Network ⋮ Political districting to minimize cut edges ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• The planar multiterminal cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• 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
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• Algorithms for Multiterminal Cuts
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Two-Commodity Flow
• 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
• 3-coloring in time
• Multiway cuts in node weighted graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Multi-Commodity Network Flows

This page was built for publication: Simple and improved parameterized algorithms for multiterminal cuts