树的彩虹控制数的一个多项式时间算法

作者：王侃, 丁佳, 王超

单位：1. 浙江师范大学数理与信息工程学院, 金华 321004;2. 华东师范大学数学系, 上海 200241;3. 华东师范大学上海市核心数学和实践重点实验室, 上海 200241

摘要：设G是一个边染色图，G的彩虹子图是所有边都染不同颜色的子图.覆盖V（G）的不相交彩虹星的集合称为彩虹控制星集，图G最小彩虹控制星集的大小称为彩虹控制数，记为γ（G）.本文给出了一个在边染色树T上寻找最小彩虹控制星集从而得到T的彩虹控制数的多项式时间算法.

关键词：彩虹控制,多项式时间算法,树

基金资助：国家自然科学基金（11371008，91230201），浙江省计算机科学与技术重中之重学科（浙江师范大学）资助项目.