Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

DOI10.1137/12086217XzbMath1312.68097arXiv1110.0259OpenAlexW2568986002MaRDI QIDQ2862207

Rajesh Chitnis, Dániel Marx, Mohammad Taghi Hajiaghayi

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.0259

zbMATH Keywords

directed graphsfixed-parameter tractabilitymultiway cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (25)

Odd Multiway Cut in Directed Acyclic Graphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Finding all leftmost separators of size \(\le k\) ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Clique Cover and Graph Separation ⋮ Hitting Selected (Odd) Cycles ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ A faster FPT algorithm for bipartite contraction ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Multi-Budgeted Directed Cuts ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Important Separators and Parameterized Algorithms ⋮ Multi-budgeted directed cuts ⋮ Acyclic Digraphs ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs

This page was built for publication: Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset