论文标题
固定树效果算法，用于边缘到相交图类
Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes
论文作者
论文摘要
对于Graph类$ \ MATHCAL {C} $，$ \ MATHCAL {C} $ - edge-deletion问题要求给定的Graph $ G $删除从$ g $的最小边数，以便以$ \ Mathcal {C} $获得图形。我们研究$ \ MATHCAL的$ \ MATHCAL {C} $ - 边缘删除问题，用于$ \ MATHCAL {C} $置换图，间隔图和其他相关图形类。从Courcelle的定理来看，这些问题是通过TreeWidth参数化时可以固定的参数。在本文中，我们为这些问题提供了具体的FPT算法。通过给出明确的算法并详细分析这些算法，我们获得的算法明显快于使用Courcelle定理获得的算法。
For a graph class $\mathcal{C}$, the $\mathcal{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 $\mathcal{C}$. We study the $\mathcal{C}$-Edge-Deletion problem for $\mathcal{C}$ the permutation graphs, 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.
