Planar graph vertex partition for linear problem kernels Academic Article

abstract

• A simple partition of the vertex set of a graph is introduced to analyze kernels for planar graph problems in which vertices and edges not in a solution have small distance to the solution. This method directly leads to improved kernel sizes for several problems, without needing new reduction rules. Moreover, new kernelization algorithms are developed for Connected Vertex Cover, Edge Dominating Set, and Maximum Triangle Packing problems, further improving the kernel sizes for these problems. 2012 Elsevier Inc.

authors

• Chen, Jianer

published proceedings

• Journal of Computer and System Sciences

author list (cited authors)

• Wang, J., Yang, Y., Guo, J., & Chen, J.

citation count

• 17

complete list of authors

• Wang, Jianxin||Yang, Yongjie||Guo, Jiong||Chen, Jianer

publication date

• August 2013

publisher

• Elsevier  Publisher

published in

• Journal of Computer and System Sciences  Journal

Digital Object Identifier (DOI)

• 10.1016/j.jcss.2012.08.001

start page

• 609

end page

• 621

volume

• 79

issue

• 5

URL

• http://dx.doi.org/10.1016/j.jcss.2012.08.001