| Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem |
| |
| 作者姓名： | JIANG He ZHANG XianChao CHEN GuoLiang |
| |
| 作者单位： | [1]School of Software, Dalian University of Technology, Dalian 116621, China; [2]Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China （Grant Nos. 60673046 and 60673066）, the Natural Science Foundation of Liaoning Province （Grant No. 20051082） and the Gifted Young Foundation of Dalian University of Technology |
| |
| 摘 要： | As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.
|
| 关 键 词： | 计算机技术 算图 最优解大比例 遗传算法 |
| 收稿时间： | 20 May 2007 |
| 修稿时间： | 2007-05-20 |
Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem |
| |
| JIANG He ZHANG XianChao CHEN GuoLiang.Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem[J].Chinese Science Bulletin,2007,52(20):2871-2875. |
| |
| Authors: | Jiang He Zhang XianChao Chen GuoLiang |
| |
| Institution: | (1) School of Software, Dalian University of Technology, Dalian, 116621, China;(2) Department of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, China |
| |
| Abstract: | As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer
science in recent years. Due to the difficulty in the research on computational complexity of the backbone, many researchers
analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing
methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP).
Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone
of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity
of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.
Supported by the National Natural Science Foundation of China (Grant Nos. 60673046 and 60673066), the Natural Science Foundation
of Liaoning Province (Grant No. 20051082) and the Gifted Young Foundation of Dalian University of Technology |
| |
| Keywords: | graph bi-partitioning problem NP-hard backbone analysis unique optimal solution instance computational complexity |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《中国科学通报(英文版)》浏览原始摘要信息 |
| 点击此处可从《中国科学通报(英文版)》下载免费的PDF全文 |
