Linear problem kernels for planar graph problems with small distance property

DOI10.1007/978-3-642-22993-0_53MaRDI QIDQ3088074zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Yongjie Yang, Jiong Guo, Jianer Chen

Publication date 17 August 2011

Published in Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22993-0_53

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Planar graph vertex partition for linear problem kernels
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Improved linear problem kernel for planar connected dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• An improved kernel for planar connected dominating set

Cited in

(8)

• Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Planar graph vertex partition for linear problem kernels
• Polynomial kernels for hard problems on disk graphs
• A \(9k\) kernel for nonseparating independent set in planar graphs
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• scientific article; zbMATH DE number 6784970 (Why is no real title available?)
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

This page was built for publication: Linear problem kernels for planar graph problems with small distance property

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