Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
复制标题
Twin-Cover：参数化算法中超越顶点覆盖
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Ganian
中科院分区：
文献类型：
--
作者：
R. Ganian
参数化算法是处理图上NP难问题的一个非常有用的工具。在这种情况下，顶点覆盖被用来作为一个强大的参数处理的问题是很难解决的，甚至在图的有界树宽度。顶点覆盖的缺点是它的边界严格限制了可接受的图类。我们引入了一个新的参数，称为双覆盖，并表明它是能够解决广泛的困难的问题，同时也比顶点覆盖限制少得多，甚至在稠密图上达到低值。
本文首先介绍了一个新的FPT算法的图Motif的有界顶点覆盖的图。这是第一个这类算法的图形Motif。我们继续定义双覆盖并提供一些相关的结果和概念。下一节包含了一些新的FPT算法上的图有界双覆盖，特别强调解决问题，这是困难的，甚至在图有界树宽。最后，第五节推广了Michael Lampis关于MS 1模型检验的最新结果，从顶点覆盖到双覆盖。
Parameterized algorithms are a very useful tool for dealing with NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with problems which are hard to solve even on graphs of bounded tree-width. The drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a new parameter called twin-cover and show that it is capable of solving a wide range of hard problems while also being much less restrictive than vertex cover and attaining low values even on dense graphs.
The article begins by introducing a new FPT algorithm for Graph Motif on graphs of bounded vertex cover. This is the first algorithm of this kind for Graph Motif. We continue by defining twin-cover and providing some related results and notions. The next section contains a number of new FPT algorithms on graphs of bounded twin-cover, with a special emphasis on solving problems which are hard even on graphs of bounded tree-width. Finally, section five generalizes the recent results of Michael Lampis for MS1 model checking from vertex cover to twin-cover.