2024-04-17T12:44:18Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002109912024-03-29T05:26:34Z01164:02592:10486:10582
Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph ClassesFixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classesenghttp://id.nii.ac.jp/1001/00210885/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=210991&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of JapanKyushu Institute of TechnologyTohoku UniversityUtrecht UniversityToshiki, SaitohRyo, YoshinakaHans, L. BodlaenderFor 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.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.AN1009593X研究報告アルゴリズム（AL）2021-AL-18315172021-04-302188-85662021-04-27