Simple and improved parameterized algorithms for multiterminal cuts
From MaRDI portal
Publication:987378
DOI10.1007/S00224-009-9215-5zbMATH Open1213.68472OpenAlexW2005309613MaRDI QIDQ987378FDOQ987378
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Beyond the flow decomposition barrier
- The Complexity of Multiterminal Cuts
- 3-coloring in time
- Multiway cuts in node weighted graphs
- Minimal multicut and maximal integer multiflow: a survey
- Parameterized graph separation problems
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Multi-Commodity Network Flows
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- An improved approximation algorithm of MULTIWAY CUT.
- Algorithms for Multiterminal Cuts
- Finding small balanced separators
- Two-Commodity Flow
- An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
- The planar multiterminal cut problem
- A simple algorithm for the planar multiway cut problem
- A 2-approximation algorithm for the directed multiway cut problem
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
Cited In (24)
- Slightly Superexponential Parameterized Problems
- An FPT algorithm for edge subset feedback edge set
- Improved parameterized and exact algorithms for cut problems on trees
- On the complexity of barrier resilience for fat regions and bounded ply
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Title not available (Why is that?)
- Title not available (Why is that?)
- A survey of parameterized algorithms and the complexity of edge modification
- Linear kernels for separating a graph into components of bounded size
- An improved approximation algorithm of MULTIWAY CUT.
- On Multiway Cut Parameterized above Lower Bounds
- How to Cut a Graph into Many Pieces
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Title not available (Why is that?)
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
- On Computing the Maximum Parsimony Score of a Phylogenetic Network
- Fixed-parameter algorithms for DAG partitioning
- The critical node detection problem in networks: a survey
- Clique Cover and Graph Separation
- On the generalized multiway cut in trees problem
- Parameterized complexity of critical node cuts
- Political districting to minimize cut edges
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- The Complexity of Multiterminal Cuts 👍 👎
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem 👍 👎
- Improved parameterized and exact algorithms for cut problems on trees 👍 👎
- Algorithms for Multiterminal Cuts 👍 👎
- Parameterized complexity of length-bounded cuts and multicuts 👍 👎
- An O *(1.84 k ) Parameterized Algorithm for the Multiterminal Cut Problem 👍 👎
- Parametrized Complexity of Length-Bounded Cuts and Multi-cuts 👍 👎
- Revisiting a simple algorithm for the planar multiterminal cut problem 👍 👎
This page was built for publication: Simple and improved parameterized algorithms for multiterminal cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987378)
