Interval deletion is fixed-parameter tractable

Yixin Cao; Dániel Marx

doi:10.1145/2629595

Interval deletion is fixed-parameter tractable

Yixin Cao, Dániel Marx

Research output: Journal article publication › Journal article › Academic research › peer-review

52 Citations (Scopus)

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.

Original language	English
Article number	21
Journal	ACM Transactions on Architecture and Code Optimization
Volume	11
Issue number	3
DOIs	https://doi.org/10.1145/2629595
Publication status	Published - 1 Jan 2014

Keywords

Algorithms

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

More information

10.1145/2629595

Cite this

@article{34e0e9b4387940ee99862fc8606a24ee,

title = "Interval deletion is fixed-parameter tractable",

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.",

keywords = "Algorithms",

author = "Yixin Cao and D{\'a}niel Marx",

year = "2014",

month = jan,

day = "1",

doi = "10.1145/2629595",

language = "English",

volume = "11",

journal = "ACM Transactions on Architecture and Code Optimization",

issn = "1544-3566",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Interval deletion is fixed-parameter tractable

AU - Cao, Yixin

AU - Marx, Dániel

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Algorithms

UR - http://www.scopus.com/inward/record.url?scp=84921490678&partnerID=8YFLogxK

U2 - 10.1145/2629595

DO - 10.1145/2629595

M3 - Journal article

SN - 1544-3566

VL - 11

JO - ACM Transactions on Architecture and Code Optimization

JF - ACM Transactions on Architecture and Code Optimization

IS - 3

M1 - 21

ER -

Interval deletion is fixed-parameter tractable

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this