Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420267 | Discrete Applied Mathematics | 2010 | 13 Pages |
Abstract
A graph G=(V,E)G=(V,E) is a 3-leaf power iff there exists a tree TT the leaf set of which is VV and such that uv∈Euv∈E iff uu and vv are at distance at most 3 in TT. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k3)O(k3) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) [8].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Stéphane Bessy, Christophe Paul, Anthony Perez,