Packing cycles faster than Erdős-Pósa

DOI10.4230/LIPICS.ICALP.2017.71zbMATH Open1441.05210OpenAlexW2730043661MaRDI QIDQ5111402FDOQ5111402

Amer E. Mouawad, Saket Saurabh, Daniel Lokshtanov, Meirav Zehavi

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7385/pdf/LIPIcs-ICALP-2017-71.pdf/

Recommendations

• Packing cycles faster than Erdős-Pósa
• The parameterized complexity of cycle packing: indifference is not an issue
• The parameterized complexity of cycle packing: indifference is not an issue
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing

zbMATH Keywords

graph algorithmsparameterized complexitycycle packingErdős-Pósa theorem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (3)

• Packing Arc-Disjoint Cycles in Tournaments
• The parameterized complexity of cycle packing: indifference is not an issue
• Packing arc-disjoint cycles in tournaments

This page was built for publication: Packing cycles faster than Erdős-Pósa

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