摘要
设G是—个边染色图,G的彩虹子图是所有边都染不同颜色的子图.覆盖V(G)的不相交彩虹星的集合称为彩虹控制星集,图G最小彩虹控制星集的大小称为彩虹控制数,记为γ(G).本文给出了—个在边染色树T上寻找最小彩虹控制星集从而得到T的彩虹控制数的多项式时间算法.
Let G be an edge-colored graph. A rainbow subgraph is a subgraph whose edges have distinct colors. A set of disjoint rainbow stars S is a rainbow dominating star set of G if S covers V（G）. The rainbow domination number of G, denoted by ^γ（G）, is the minimum cardinality of a rainbow dominating star set. A polynomial-time algorithm is proposed in this paper for finding a minimum rainbow dominating star set and hence the value ^γ（T） for an edge-colored tree T.
作者
王侃
丁佳
王超
WANG KAN DING JIA WANG CHAO(College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China Department of Mathematics, East China Normal University, Shanghai 200241, China Shanghai key laboratory of PMMP, East China Normal University, Shanghai 200241, China)
出处
《应用数学学报》
CSCD
北大核心
2017年第1期66-72,共7页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金(11371008
91230201)
浙江省计算机科学与技术重中之重学科(浙江师范大学)资助项目
关键词
彩虹控制
多项式时间算法
树
rainbow domination
polynomial-time algorithm
tree
