@inproceedings{7646d75bcdee4fc0afc1a7f0550902d9,
title = "Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes",
abstract = "For a graph class C, the C -Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C -Edge-Deletion problem for C the class of interval graphs and other related graph classes. It follows from Courcelle{\textquoteright}s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle{\textquoteright}s theorem.",
keywords = "Edge-Deletion, Interval graphs, Parameterized algorithms, Treewidth",
author = "Toshiki Saitoh and Ryo Yoshinaka and Bodlaender, {Hans L.}",
note = "Funding Information: Acknowledgement. This work was supported in part by JSPS KAKENHI Grant Numbers JP18H04091 and JP19K12098. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 15th International Conference on Algorithms and Computation, WALCOM 2021 ; Conference date: 28-02-2021 Through 02-03-2021",
year = "2021",
doi = "10.1007/978-3-030-68211-8_12",
language = "English",
isbn = "9783030682101",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "142--153",
editor = "Ryuhei Uehara and Seok-Hee Hong and Nandy, {Subhas C.}",
booktitle = "WALCOM",
address = "Germany",
}