Parameterized complexity of weighted multicut in trees

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

zbMATH Keywords

directed flow augmentationweighted digraph pair cutweighted multicut in trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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