| 求图符号控制数的完全算法研究 |
| |
| 引用本文： | 陈卫东. 求图符号控制数的完全算法研究[J]. 计算机工程与应用, 2004, 40(24): 45-47,53 |
| |
| 作者姓名： | 陈卫东 |
| |
| 作者单位： | 华南师范大学计算机系,广州,510631 |
| |
| 基金项目： | 国家自然科学基金资助项目(编号:10201009)，广东省自然科学基金资助项目(编号:021072) |
| |
| 摘 要： | 确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五。对这两个算法也进行了比较。
|
| 关 键 词： | 图 符号控制数 NP难度 回溯法 分枝定界法 A*算法 |
| 文章编号： | 1002-8331-(2004)24-0045-03 |
Exact Algorithms for the Signed Domination Number of a Graph |
| |
| Chen Weidong. Exact Algorithms for the Signed Domination Number of a Graph[J]. Computer Engineering and Applications, 2004, 40(24): 45-47,53 |
| |
| Authors: | Chen Weidong |
| |
| Abstract: | To obtain efficient strict algorithms for determining the signed domination number in a graph which is NP-hard,some heuristic bounding strategies are proposed.Based on these strategies a backtracking algorithm and an Aal-gorithm are presented.The experimental results show that less than five vertices in a thousand vertices in the state space tree are generated during running these algorithms on every random instance.These algorithms are also compared. |
| |
| Keywords: | graph signed domination number NP-hardness backtracking branch-and-bound Aalgorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
