| 加权分治与皇冠技术求解最大加权独立集 |
| |
| 引用本文： | 刘志民,宁爱兵,黄 飞,何咏梅,张惠珍. 加权分治与皇冠技术求解最大加权独立集[J]. 计算机工程与应用, 2017, 53(9): 26-30. DOI: 10.3778/j.issn.1002-8331.1612-0474 |
| |
| 作者姓名： | 刘志民 宁爱兵 黄 飞 何咏梅 张惠珍 |
| |
| 作者单位： | 上海理工大学 管理学院，上海 200093 |
| |
| 摘 要： | 皇冠分解技术是一种算法优化技术，通过找出一个称为皇冠的特殊非空独立集，并将该独立集和它的邻接集合删除，得到一个不含皇冠的子图，从而降低原问题规模，降低算法时间复杂度。针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图，并通过该图找出皇冠结构，采用皇冠分解技术分解图，针对无皇冠的子图设计了一个分支降阶递归算法，然后利用加权分治技术对算法时间复杂度进行分析，最终得到一个优于常规时间复杂度的精确算法。
|
| 关 键 词： | 皇冠分解 加权独立集 加权分治算法 分支降阶 |
Measure and conquer and crown technology to solve maximum weighted independent set |
| |
| LIU Zhimin,NING Aibing,HUANG Fei,HE Yongmei,ZHANG Huizhen. Measure and conquer and crown technology to solve maximum weighted independent set[J]. Computer Engineering and Applications, 2017, 53(9): 26-30. DOI: 10.3778/j.issn.1002-8331.1612-0474 |
| |
| Authors: | LIU Zhimin NING Aibing HUANG Fei HE Yongmei ZHANG Huizhen |
| |
| Affiliation: | School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China |
| |
| 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. |
| |
| Keywords: | crown decomposition weighted independent set measure and conquer branch and reduction |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
|
