Back to Search
Start Over
Polynomial kernels for 3-leaf power graph modification problems
- Source :
-
Discrete Applied Mathematics . Aug2010, Vol. 158 Issue 16, p1732-1744. 13p. - Publication Year :
- 2010
-
Abstract
- Abstract: A graph is a 3-leaf power iff there exists a tree the leaf set of which is and such that iff and are at distance at most 3 in . 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 vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 158
- Issue :
- 16
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 53381551
- Full Text :
- https://doi.org/10.1016/j.dam.2010.07.002