An exact algorithm for maximum independent set in degree-5 graphs
An exact algorithm for maximum independent set in degree-5 graphs
复制标题
DOI：
10.1016/j.dam.2014.07.009
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Mingyu Xiao;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Mingyu Xiao;H. Nagamochi
最大独立集问题是一个基本的np困难问题，在精确算法中得到了广泛的研究。低次图中的最大独立集问题也很重要，可能是一般图问题的瓶颈。本文针对度限为5的非顶点图的最大独立集问题，提出了anO*(1.1737n)时间精确算法，改进了以往o *(1.1895n)的运行时间界限。在算法中，我们引入了一种有效的分治法来处理图中最多两个的顶点切割，并设计了最大次数为5的三连通图的一些特殊结构的分支规则。这些结果在不引入大量分支规则的情况下改进了算法。
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present anO*(1.1737n)-time exact algorithm for the maximum independent set problem in ann-vertex graph with degree bounded by 5, improving the previous running time bound ofO*(1.1895n). In our algorithm, we introduce an effective divide-and-conquer procedure to deal with vertex cuts of size at most two in graphs, and design branching rules on some special structures of triconnected graphs of maximum degree 5. These result in an improved algorithm without introducing a large number of branching rules.