论文研究-加权分治与皇冠技术求解最大加权独立集.pdf

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