摘要
最大团问题(maximum clique problem,MCP)是图论中的一个经典组合优化问题,也是一类NP完全问题,在国际上已有广泛地研究,国内研究刚刚起步。给出了最大团问题的基本定义和其数学描述;阐述了该问题的研究进展;分析和研究了求解该问题的各种典型启发式算法,包括算法的介绍、算法求解最大团问题的基本思路、特点及性能;最后介绍了测试这些启发式算法性能的测试基准图。
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 described.
出处
《计算机工程与设计》
CSCD
北大核心
2007年第18期4329-4332,共4页
Computer Engineering and Design
基金
国家自然科学基金项目(60473012)
国家科技攻关基金项目(2003BA614A-14)
江苏省自然科学基金项目(BK2005047)。
关键词
最大团问题
启发式算法
组合优化
确定性算法
图
maximum clique problem （MCP）
heuristic algorithm
combinatorial optimization
exact algorithm
graph
