Kernelization of cycle packing with relaxed disjointness constraints

DOI10.4230/LIPICS.ICALP.2016.26zbMATH Open1388.68097MaRDI QIDQ4598162FDOQ4598162

Authors: Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, Saket Saurabh 

Publication date: 19 December 2017

Recommendations

• Kernelization of cycle packing with relaxed disjointness constraints
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Edge-disjoint packing of stars and cycles
• Kernel bounds for disjoint cycles and disjoint paths
• Edge-disjoint packing of stars and cycles

zbMATH Keywords

parameterized complexityrelaxationkernelizationcycle packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (6)

• Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths
• The parameterized complexity of cycle packing: indifference is not an issue
• Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Kernelization of cycle packing with relaxed disjointness constraints
• Arbitrary overlap constraints in graph packing problems

This page was built for publication: Kernelization of cycle packing with relaxed disjointness constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598162)