A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs (Extended Abstract)

摘要

We present a simple O* (1.0885~n)-time algorithm for finding a maximum independent set in an n-vertex graph with degree bounded by 3, which improves most previous running time bounds obtained with far more complicated algorithms. In this paper, we use a nontraditional measure to analyze the problem size and some uniform branching rules to avoid tedious case analysis. Those techniques help us to design simple and fast algorithms with moderately complicated analysis.