Abstract
We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph on n vertices into an interval graph. We present a parameterized algorithm of runtime 10k. nO(1)for this problem, thereby showing its fixed-parameter tractability.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
| Publisher | Association for Computing Machinery |
| Pages | 122-141 |
| Number of pages | 20 |
| ISBN (Print) | 9781611973389 |
| Publication status | Published - 1 Jan 2014 |
| Externally published | Yes |
| Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: 5 Jan 2014 → 7 Jan 2014 |
Conference
| Conference | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
|---|---|
| Country/Territory | United States |
| City | Portland, OR |
| Period | 5/01/14 → 7/01/14 |
ASJC Scopus subject areas
- Software
- General Mathematics