弦图子类的全控制函数

作者：周立刚; 单而芳; 王海超

来源：运筹学学报, 2010, (01): 85-94.

DOI：10.15960/j.cnki.issn.1007-6093.2010.01.009

• 运筹学
• 全控制函数
• 符号全控制
• 负全控制
• 强弦图
• 双弦图 Operations research
• total dominating function
• signed total domination
• minus total domination
• strongly chordal graphs
• doubly chordal graphs

本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和{k}-全控制问题的统一的O(m n)时间算法.

• 出版日期2010
• 单位上海电力大学; 上海大学