| 弦图子类的全控制函数 |
| |
| 引用本文： | 周立刚,单而芳,王海超.弦图子类的全控制函数[J].运筹学学报,2010,14(1):85-94. |
| |
| 作者姓名： | 周立刚 单而芳 王海超 |
| |
| 作者单位： | 1. 上海大学理学院数学系,上海,200444
2. 上海电力学院数理系,上海,200090 |
| |
| 基金项目： | 国家自然科学基金，上海市重点学科建设项目 |
| |
| 摘 要： | 本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次，在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和k-全控制问题的统一的O(m+n)时间算法.
|
| 关 键 词： | 运筹学 全控制函数 符号全控制 负全控制 强弦图 双弦图 |
Total Dominating Functions on Subclasses of Chordal Graphs |
| |
| Zhou Ligang,Shan Erfang,Wang Haichao.Total Dominating Functions on Subclasses of Chordal Graphs[J].OR Transactions,2010,14(1):85-94. |
| |
| Authors: | Zhou Ligang Shan Erfang Wang Haichao |
| |
| Institution: | Zhou Ligang Shan Erfang Wang Haichao Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,China. Department of Mathematics , Physics,Shanghai University of Electric Power,Shanghai 200090,China. |
| |
| Abstract: | In this paper we show that the k-total domination and signed total domination problems are NP-complete on doubly chordal graphs.Also,we present an unified approach to slove the signed total domination,minus total domination,k-total domination and {k}-total domination problems on a strongly chordal graph in lineartime, if the strong elemination ordering for the strongly chordal graph is given. |
| |
| Keywords: | Operations research total dominating function signed total domination minus total domination strongly chordal graphs doubly chordal graphs |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
