A Polynomial Kernel for Proper Interval Vertex Deletion
From MaRDI portal
Publication:5408603
DOI10.1137/12089051XzbMATH Open1285.05160arXiv1204.4880OpenAlexW2088722899WikidataQ60488412 ScholiaQ60488412MaRDI QIDQ5408603
Author name not available (Why is that?)
Publication date: 10 April 2014
Published in: (Search for Journal in Brave)
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 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.
Full work available at URL: https://arxiv.org/abs/1204.4880
No records found.
No records found.
This page was built for publication: A Polynomial Kernel for Proper Interval Vertex Deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408603)
