摘要： 针对具有NP难度的图符号控制数问题,沿着拟人的途径,制定了若干求解策略,给出了一个启发式算法即Local-Search-SDN算法。通过与完全算法的比较,实验结果表明Local-Search-SDN算法能快速找到问题的高质量解。

关键词: 图, 符号控制数, NP难度, 拟人, 启发式算法

Abstract: This pagerstudiesalgorithmsfordeterminingthesigneddominationnumberinagraph.Somepersonificationstrategiesoftacklingitareproposedbasedon personification, and a heuristic algorithm named Local-Search-SDN is presented. The experimental results show that the performance of Local-Search-SDN is very good in both the solution quality and the execution time.

中图分类号: 

• TP301.6