Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Better Polynomial Algorithms on Graphs of Bounded Rank-Width
复制标题
有界秩宽图上更好的多项式算法
DOI：
10.1007/978-3-642-10217-2_27
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Petr Hliněný
中科院分区：
文献类型：
--
作者：
R. Ganian;Petr Hliněný
对于np困难问题，虽然已有许多多项式算法运行在输入图的有界团宽度表达式上，但对于秩宽度的算法却很少有类似的研究。我们认为，造成这种情况的一个原因是等级分解有些模糊和难以掌握的性质。然而，最近由Courcelle和Kante、作者和Bui-Xuan等人独立开发的形式化给出了使用rank-width参数的有力论据。本文的重点是设计形式上清晰易懂的“伪多项式”（XP）算法，解决有界秩-宽度图上的“难”问题（非fpt）。这些问题包括计算色数和多项式或检验图的哈密性，并可扩展到许多其他问题。
Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kante, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems.