| 二部置换图的无圈控制集算法 |
| |
| 引用本文： | 许光俊,康丽英,赵敏. 二部置换图的无圈控制集算法[J]. 上海大学学报(自然科学版), 2006, 12(1): 14-18 |
| |
| 作者姓名： | 许光俊 康丽英 赵敏 |
| |
| 作者单位： | 上海大学,理学院,上海,200444 |
| |
| 基金项目： | 中国科学院资助项目;上海市重点学科建设项目;上海市教委资助项目 |
| |
| 摘 要： | 设G=(V,E)为简单无向图,S V称为G的无圈控制集,如果S控制G并且导出子图〈S〉不含有圈.该文证明了二部置换图的无圈控制数等于其控制数(γa(G)=γ(G)),利用此结论证明了无圈控制集问题在二部置换图上具有线性时间求解算法.
|
| 关 键 词： | 二部置换图 控制集 无圈控制集 算法 |
| 文章编号： | 1007-2861（2006）01-0014-05 |
| 收稿时间： | 2004-11-16 |
| 修稿时间： | 2004-11-16 |
Algorithm of Acyclic Dominating Set Problem on Bipartite Permutation Graphs |
| |
| XU Guang-jun,KANG Li-ying,ZHAO Min. Algorithm of Acyclic Dominating Set Problem on Bipartite Permutation Graphs[J]. Journal of Shanghai University(Natural Science), 2006, 12(1): 14-18 |
| |
| Authors: | XU Guang-jun KANG Li-ying ZHAO Min |
| |
| Affiliation: | School of Sciences, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | |
| |
| Keywords: | bipartite permutation graph dominating set acyclic dominating set algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
