Simple and improved parameterized algorithms for multiterminal cuts
From MaRDI portal
Publication:987378
DOI10.1007/s00224-009-9215-5zbMath1213.68472OpenAlexW2005309613MaRDI QIDQ987378
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
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
