English

运筹学学报 ›› 2010, Vol. 14 ›› Issue (1): 85-94.

• 运筹学 • 上一篇    下一篇

弦图子类的全控制函数

周立刚, 单而芳, 王海超   

  • 出版日期:2010-03-15 发布日期:2010-03-15

Total Dominating Functions on Subclasses    of Chordal Graphs

ZHOU Li-Gang, DAN 而Fang, WANG Hai-Chao   

  • Online:2010-03-15 Published:2010-03-15

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

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 linear-time, if the strong elemination ordering for the strongly chordal graph is given.