Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/16184
Title: Interval deletion is fixed-parameter tractable
Authors: Cao, Y
Marx, D
Keywords: Algorithms
Issue Date: 2014
Publisher: Association for Computing Machinery
Source: ACM transactions on architecture and code optimization, 2014, v. 11, no. 3, 21 How to cite?
Journal: ACM Transactions on Architecture and Code Optimization 
Abstract: We study the minimum interval deletion problem, which asks for the removal of a set of at most κ vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10κ · nO(1) for this problem-that is, we show that the problem is fixed-parameter tractable.
URI: http://hdl.handle.net/10397/16184
ISSN: 1544-3566
DOI: 10.1145/2629595
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

5
Last Week
0
Last month
0
Citations as of May 15, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
0
Citations as of May 22, 2017

Page view(s)

23
Last Week
1
Last month
Checked on May 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.