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.
|Journal||ACM Transactions on Architecture and Code Optimization|
|Publication status||Published - 1 Jan 2014|
ASJC Scopus subject areas
- Information Systems
- Hardware and Architecture