Simple and improved parameterized algorithms for multiterminal cuts
From MaRDI portal
Publication:987378
DOI10.1007/S00224-009-9215-5zbMATH Open1213.68472OpenAlexW2005309613MaRDI QIDQ987378FDOQ987378
Recommendations
- An improved parameterized algorithm for the multicut problem
- Algorithms for Multiterminal Cuts
- Revisiting a simple algorithm for the planar multiterminal cut problem
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
- An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem
- scientific article; zbMATH DE number 1775387
- Parameterized complexity of length-bounded cuts and multicuts
- Improved parameterized and exact algorithms for cut problems on trees
- The Complexity of Multiterminal Cuts
- Parametrized complexity of length-bounded cuts and multi-cuts
Cites work
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- 3-coloring in time
- A 2-approximation algorithm for the directed multiway cut problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- A simple algorithm for the planar multiway cut problem
- 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
- An improved approximation algorithm of MULTIWAY CUT.
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Beyond the flow decomposition barrier
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- Finding small balanced separators
- Minimal multicut and maximal integer multiflow: a survey
- Multi-Commodity Network Flows
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Multiway cuts in node weighted graphs
- Parameterized graph separation problems
- The Complexity of Multiterminal Cuts
- The planar multiterminal cut problem
- Two-Commodity Flow
Cited in
(28)- Slightly superexponential parameterized problems
- The critical node detection problem in networks: a survey
- Algorithms for Multiterminal Cuts
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Linear kernels for separating a graph into components of bounded size
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
- An FPT algorithm for edge subset feedback edge set
- An improved parameterized algorithm for the multicut problem
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Clique Cover and Graph Separation
- How to Cut a Graph into Many Pieces
- An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Political districting to minimize cut edges
- Faster exact algorithms for some terminal set problems
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- On computing the maximum parsimony score of a phylogenetic network
- On the generalized multiway cut in trees problem
- An improved approximation algorithm of MULTIWAY CUT.
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized complexity of critical node cuts
- Fixed-parameter algorithms for DAG partitioning
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Improved parameterized and exact algorithms for cut problems on trees
- On the complexity of barrier resilience for fat regions and bounded ply
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)
