Polynomial kernels for 3-leaf power graph modification problems

Details Polynomial kernels for 3-leaf power graph modification problems Polynomial kernels for 3-leaf power graph modification problems

2008-09-17

arxiv.org/abs/0809.2858v2

Computer Science

Discrete Mathematics

Submitted

Scientific paper

A graph G=(V,E) is a 3-leaf power iff there exists a tree T whose leaves are V and such that (u,v) is an edge iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion, are FTP when parameterized by the size of the edge set modification. However polynomial kernel was known for none of these three problems. For each of them, we provide cubic kernels that can be computed in linear time for each of these problems. We thereby answer an open problem first mentioned by Dom, Guo, Huffner and Niedermeier (2005).

Affiliated with

Also associated with

No associations

Rating

Polynomial kernels for 3-leaf power graph modification problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial kernels for 3-leaf power graph modification problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial kernels for 3-leaf power graph modification problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661336