Unit interval vertex deletion: Fewer vertices are relevant

作者：

Highlights：

• Significant improvement of kernel size of a well-studied problem from k53 to k4.

• Simplicity of the algorithm and especially its analysis.

• Efficient implementation of O(mn+n2) time.

摘要

•Significant improvement of kernel size of a well-studied problem from k53 to k4.•Simplicity of the algorithm and especially its analysis.•Efficient implementation of O(mn+n2) time.

论文关键词：Unit interval graph,Kernelization,Graph modification problem,Forbidden induced subgraph,(Proper, unit) interval model,Modulator

论文评审过程：Received 12 December 2016, Revised 16 January 2018, Accepted 27 January 2018, Available online 3 March 2018, Version of Record 30 April 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.01.001