A POLYNOMIAL KERNEL FOR MULTICUT IN TREES

DOI10.4230/LIPIcs.STACS.2009.1824zbMath1236.68104OpenAlexW2172205830MaRDI QIDQ5389976

Anders Yeo, Jean Daligault, Steéphan Thomassé, Nicolas Bousquet

Publication date: 24 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_1091.html

zbMATH Keywords

polynomial kernelkernelizationmulticut in trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05)

Related Items (11)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ Multicut Is FPT ⋮ On the generalized multiway cut in trees problem ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Kernels for feedback arc set in tournaments ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Kernelization: New Upper and Lower Bound Techniques

This page was built for publication: A POLYNOMIAL KERNEL FOR MULTICUT IN TREES