Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
From MaRDI portal
Publication:2862207
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
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
