Parameterized complexity of weighted multicut in trees
From MaRDI portal
Publication:6039425
DOI10.1007/978-3-031-15914-5_19arXiv2205.10105MaRDI QIDQ6039425
Esther Galby, Dániel Marx, Roohani Sharma, Prafullkumar Tale, Philipp Schepper
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2205.10105
Related Items (2)
An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ On Weighted Graph Separation Problems and Flow Augmentation
Cites Work
- Unnamed Item
- Multicut in trees viewed through the eyes of vertex cover
- List H-coloring a graph by removing few vertices
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Parameterized graph separation problems
- Exact algorithms and applications for tree-like Weighted Set Cover
- Clustering with local restrictions
- Parameterized Tractability of Multiway Cut with Parity Constraints
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- Algorithms for Cut Problems on Trees
- Fixed-parameter tractability and data reduction for multicut in trees
- The Complexity of Multiterminal Cuts
- Multicut Is FPT
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Representative Sets and Irrelevant Vertices
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Parameterized Algorithms
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
This page was built for publication: Parameterized complexity of weighted multicut in trees
