Fomin, Fedor V. ; Saurabh, Saket ; Villanger, Yngve (2013) A Polynomial Kernel for Proper Interval Vertex Deletion SIAM Journal on Discrete Mathematics, 27 (4). pp. 1964-1976. ISSN 0895-4801
Full text not available from this repository.
Official URL: http://doi.org/10.1137/12089051X
Related URL: http://dx.doi.org/10.1137/12089051X
Abstract
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 answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |
| ID Code: | 123437 |
| Deposited On: | 16 Sep 2021 11:32 |
| Last Modified: | 16 Sep 2021 11:32 |
Repository Staff Only: item control page
