A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs

DOI10.1007/978-3-540-92182-0_29zbMATH Open1183.68412DBLPconf/isaac/BodlaenderPT08OpenAlexW1578674049WikidataQ59567710 ScholiaQ59567710MaRDI QIDQ3596728FDOQ3596728

Authors: Eelko Penninkx, Richard B. Tan, Hans L. Bodlaender 

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_29

Recommendations

• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Improved kernels for several problems on planar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Paths and cycles (05C38)

Cited In (12)

• A linear kernel for a planar connected dominating set
• A Retrospective on (Meta) Kernelization
• Packing cycles faster than Erdős-Pósa
• Title not available (Why is that?)
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Title not available (Why is that?)
• Kernel bounds for disjoint cycles and disjoint paths
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Graph-Theoretic Concepts in Computer Science
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Bidimensionality and kernels

This page was built for publication: A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs

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