Multicut in trees viewed through the eyes of vertex cover

DOI10.1016/j.jcss.2012.03.001zbMath1244.68039OpenAlexW2007342225MaRDI QIDQ440014

Fenghui Zhang, Jia-Hao Fan, Yang Liu, Iyad A. Kanj, Jian'er Chen

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2012.03.001

zbMATH Keywords

parameterized algorithmsparameterized complexitykernelizationmulticut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (7)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Multicut Is FPT ⋮ On the generalized multiway cut in trees problem

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• Fixed-parameter tractability and data reduction for multicut in trees
• Nondeterminism within $P^ * $
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multicut in trees viewed through the eyes of vertex cover