| 启发式算法求解最大团问题研究 |
| |
| 引用本文： | 周旭东,王丽爱,陈崚. 启发式算法求解最大团问题研究[J]. 计算机工程与设计, 2007, 28(18): 4329-4332 |
| |
| 作者姓名： | 周旭东 王丽爱 陈崚 |
| |
| 作者单位： | 扬州大学,信息工程学院计算机中心,江苏,扬州,225009;扬州大学,信息工程学院计算机系,江苏,扬州,225009;扬州大学,信息工程学院计算机中心,江苏,扬州,225009;扬州大学,信息工程学院计算机系,江苏,扬州,225009;南京大学,软件新技术国家重点实验室,江苏,南京,210093 |
| |
| 基金项目： | 国家自然科学基金 , 国家科技攻关计划 , 江苏省自然科学基金 |
| |
| 摘 要： | 最大团问题(maximum clique problem,MCP)是图论中的一个经典组合优化问题,也是一类NP完全问题,在国际上已有广泛地研究,国内研究刚刚起步.给出了最大团问题的基本定义和其数学描述;阐述了该问题的研究进展;分析和研究了求解该问题的各种典型启发式算法,包括算法的介绍、算法求解最大团问题的基本思路、特点及性能;最后介绍了测试这些启发式算法性能的测试基准图.
|
| 关 键 词： | 最大团问题 启发式算法 组合优化 确定性算法 图 |
| 文章编号： | 1000-7024（2007）08-4329-04 |
| 修稿时间： | 2006-09-28 |
Research on using heuristic algorithms to solve MCP |
| |
| ZHOU Xu-dong,WANG Li-ai,CHEN Ling. Research on using heuristic algorithms to solve MCP[J]. Computer Engineering and Design, 2007, 28(18): 4329-4332 |
| |
| Authors: | ZHOU Xu-dong WANG Li-ai CHEN Ling |
| |
| Affiliation: | 1. Computer Center, College of Information, Yangzhou University, Yangzhou 225009, China; 2. Department of Computer, College of Information, Yangzhou University, Yangzhou 225009, China; 3. National Key Lab of Novel Software Technology, Nanjing University, Nanjing 210093, China |
| |
| Abstract: | The maximum clique problem (MCP) is a classical problem of combinatorial optimization in graph theory, and is a kind of NP-Complete problem. MCP has been widely researched internationally, however, in china the research of it is just beginning. The definition of MCP is described; the development about using heuristic algorithms to solve MCP is expounded; a variety of typically heu- ristic algorithms solving MCP are analyzed and researched, including introducing about these algorithms, their basic ideas and charac- teristics and performances about solving MCP. Finally the test benchmark graphs for testing the performance of these algorithms are de- scribed. |
| |
| Keywords: | maximum clique problem (MCP) heuristic algorithm combinatorial optimization exact algorithm graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
