Multicut Is FPT
From MaRDI portal
Publication:4605273
DOI10.1137/140961808zbMath1380.05184arXiv1010.5197OpenAlexW2785454599MaRDI QIDQ4605273
Jean Daligault, Steéphan Thomassé, Nicolas Bousquet
Publication date: 22 February 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.5197
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Quick separation in chordal and split graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multicut in trees viewed through the eyes of vertex cover
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Minimal multicut and maximal integer multiflow: a survey
- Parameterized graph separation problems
- A polyhedral approach to an integer multicommodity flow problem
- A logical approach to multicut problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- On the hardness of approximating Multicut and Sparsest-Cut
- Parametrized complexity theory.
- Clique Cover and Graph Separation: New Incompressibility Results
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- On Multiway Cut Parameterized above Lower Bounds
- Finding small separators in linear time via treewidth reduction
- Intersection Theorems for Systems of Sets
- Fixed-parameter tractability and data reduction for multicut in trees
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
- The Complexity of Multiterminal Cuts
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Representative Sets and Irrelevant Vertices
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- Multicut is FPT
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- SOFSEM 2006: Theory and Practice of Computer Science
This page was built for publication: Multicut Is FPT
