A Polynomial kernel for Proper Interval Vertex Deletion

Details A Polynomial kernel for Proper Interval Vertex Deletion A Polynomial kernel for Proper Interval Vertex Deletion

2012-04-22

arxiv.org/abs/1204.4880v1

Computer Science

Data Structures and Algorithms

13 pages, 1 figure

Scientific paper

It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answers this question in affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern, Komusiewicz, Moser, and Niedermeier.

Affiliated with

Also associated with

No associations

Rating

A Polynomial kernel for Proper Interval Vertex Deletion 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 A Polynomial kernel for Proper Interval Vertex Deletion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial kernel for Proper Interval Vertex Deletion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-522799