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.%皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度.针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集.首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法.
展开▼
