关键词: 皇冠分解, 加权独立集, 加权分治算法, 分支降阶

Abstract: Crown decomposition technique is an optimal technique for algorithm. The central idea of crown decomposition is searching a special non-empty independent set called crown, removing it and its neighboring points from the graph, and leaving a sub-graph without crown. After that, it can reduce scale for the original problem, and eventually reduce the time complexity. In a weighted graph, based on characters relating to independent sets, this paper designs an exact algorithm to find a weighted independent set with maximum weight. Firstly, it constructs a binary graph and finds the crown structure via the binary graph. After partitioning a graph with the crown decomposition technique, it designs a branch and reduction recursive algorithm for a crown-free sub-graph. Then, depending on the crown reduce and measure and conquer technology, it analyzes the time complexity. Finally, it gets an exact algorithm, which is superior to the conventional time complexity.

Key words: crown decomposition, weighted independent set, measure and conquer, branch and reduction