論文

査読有り 筆頭著者 国際共著
2021年1月

Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Saitoh T
  • ,
  • Yoshinaka R
  • ,
  • Bodlaender H.L

12635 LNCS
開始ページ
142
終了ページ
153
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-030-68211-8_12

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’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’s theorem.

リンク情報
DOI
https://doi.org/10.1007/978-3-030-68211-8_12
URL
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85102762814&origin=inward
ID情報
  • DOI : 10.1007/978-3-030-68211-8_12

エクスポート
BibTeX RIS