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

DOI10.1007/978-3-540-92182-0_29MaRDI QIDQ3596728zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

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
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• scientific article; zbMATH DE number 219251 (Why is no real title available?)
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• scientific article; zbMATH DE number 4135967 (Why is no real title available?)
• Kernel bounds for disjoint cycles and disjoint paths
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Graph-Theoretic Concepts in Computer Science
• 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)