On the small cycle transversal of planar graphs |
| |
Authors: | Ge Xia Yong Zhang |
| |
Affiliation: | a Department of Computer Science, Lafayette College, Easton, PA 18042, USAb Department of Computer Science, Kutztown University, Kutztown, PA 19530, USA |
| |
Abstract: | We consider the problem of finding a k-edge transversal set that intersects all (simple) cycles of length at most s in a planar graph, where s≥3 is a constant. This problem, referred to as Small Cycle Transversal, is known to be NP-complete. We present a polynomial-time algorithm that computes a kernel of size 36s3k for Small Cycle Transversal. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. (2004) 1] by considering a unique region decomposition that is defined by shortest paths. Our kernel size is a significant improvement in terms of s over the kernel size obtained under the meta-kernelization framework by Bodlaender et al. (2009) 7]. |
| |
Keywords: | Parameterized complexity Kernelization Planar graphs Cycle transversal |
本文献已被 ScienceDirect 等数据库收录! |
|