弦图子类的全控制函数  

Total Dominating Functions on Subclasses of Chordal Graphs

作　　者：周立刚[1] 单而芳[1] 王海超[2] 

机构地区：[1]上海大学理学院数学系,上海200444 [2]上海电力学院数理系,上海200090

出　　处：《运筹学学报》2010年第1期85-94,共10页Operations Research Transactions

基　　金：国家自然科学基金资助项目(No.60773078);上海市重点学科(No.S30104)支持项目

摘　　要：本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和{k}-全控制问题的统一的O(m+n)时间算法.In this paper we show that the κ-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, κ-total domination and {κ}-total domination problems on a strongly chordal graph in lineartime, if the strong elemination ordering for the strongly chordal graph is given.

关 键 词：运筹学 全控制函数 符号全控制 负全控制 强弦图 双弦图 

分 类 号：O157.5[理学—数学]