An exact algorithm for maximum independent set in degree-5 graphs

作者：Xiao, Mingyu^*; Nagamochi, Hiroshi

来源：Discrete Applied Mathematics, 2016, 199: 137-155.

DOI：10.1016/j.dam.2014.07.009

• Exact algorithm
• Graph algorithm
• Maximum independent set
• Measure and Conquer
• Amortized analysis

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 a 1.1736(n)n(0(1))-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895(n)n(0(1)). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules.

• 出版日期2016-1-30
• 单位电子科技大学