树的彩虹控制数的一个多项式时间算法 王侃^1,2, 丁佳^2,3, 王超^2,31. 浙江师范大学数理与信息工程学院, 金华 321004;
2. 华东师范大学数学系, 上海 200241;
3. 华东师范大学上海市核心数学和实践重点实验室, 上海 200241 A Polynomial-time Algorithm for Rainbow Domination in Trees WANG Kan^1,2, DING Jia^2,3, WANG Chao^2,31. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China;
2. Department of Mathematics, East China Normal University, Shanghai 200241, China;
3. Shanghai key laboratory of PMMP, East China Normal University, Shanghai 200241, China

摘要 图/表 参考文献(0) 相关文章(15) 点击分布统计 下载分布统计 --> 全文: PDF(296 KB) HTML (1 KB) 输出: BibTeX | EndNote (RIS) 摘要设G是一个边染色图，G的彩虹子图是所有边都染不同颜色的子图.覆盖V（G）的不相交彩虹星的集合称为彩虹控制星集，图G最小彩虹控制星集的大小称为彩虹控制数，记为γ（G）.本文给出了一个在边染色树T上寻找最小彩虹控制星集从而得到T的彩虹控制数的多项式时间算法. 服务 加入引用管理器 E-mail Alert RSS 收稿日期: 2014-12-15 PACS: O157.5 基金资助:国家自然科学基金（11371008，91230201），浙江省计算机科学与技术重中之重学科（浙江师范大学）资助项目. 引用本文: 王侃, 丁佳, 王超. 树的彩虹控制数的一个多项式时间算法[J]. 应用数学学报, 2017, 40(1): 66-72. WANG Kan, DING Jia, WANG Chao. A Polynomial-time Algorithm for Rainbow Domination in Trees. Acta Mathematicae Applicatae Sinica, 2017, 40(1): 66-72. 链接本文: http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2017/V40/I1/66 [1] Albert M, Frieze A, Reed B. Multicoloured Hamilton cycles. Electron. J. Combin., 1995, 2:#R10 [2] Alon N, Jiang T, Miller Z, Pritikin D. Properly colored subgraphs and rainbow subgraphs in edge colorings with local constraints. Random Structures Algorithms, 2003, 23(4):409-433 [3] Hahn G, Thomassen C. Path and cycle sub-Ramsey numbers and an edge colouring conjecture. Discrete Math., 1986, 62(1):29-33 [4] Kostochka A, Yancey M. Large rainbow matchings in edge-coloured graphs. Combin. Probab. Comput., 2012, 21(1-2):255-263 [5] Suzuki, K. A necessary and sufficient contidion for the existence of a heterochromatic spanning tree in a graph. Graphs Combin., 2006, 22(2):261-269 [6] Wang G H, Li H. Heterochromatic matchings in edge-colored graphs. Electron. J. Combin., 2008, 15:#R138 [7] Kano M, Li X L. Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. Graphs Combin., 2008, 24(4):237-263 [8] Li X L, Shi Y T, Sun Y F. Rainbow connections of graphs:a survey. Graphs Combin., 2013, 29(1):1-38 [9] LeSaulnier T D, West D B. Rainbow edge-coloring and rainbow domination. Discrete Math., 2013, 313(19):2020-2025 [10] Diestel R. Graph Theory, 4th ed. Graduate Texts in Mathematics, Springer, 2010 [11] Chang G J. Algorithmic aspects of domination in graphs, Vol. 3, In:Handbook of Combinatorial Optimization, ed. by Du D Z, Pardalos P M, 1998, 339-405 [12] Chen, L, Lu, C, Zeng Z. Labelling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim., 2010, 19(4):457-470 [13] Chen L, Lu C H, Zeng Z B. A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inform. Process. Lett., 2009, 110(1):20-23 [14] Cheng T C E, Kang L Y, Shan E F. A polynomial-time algorithm for the paired domination problem on permutation graphs. Discrete Appl. Math., 2009, 157(2):262-271 [1] 傅云斌, 颜云志, 唐堰, 胡细, 王汉兴. 一类生灭分枝树模型[J]. 应用数学学报, 2016, 39(5): 734-747. [2] 廖云华, 谢小良. 两点连图的Tutte多项式及其应用[J]. 应用数学学报, 2016, 39(3): 392-402. [3] 张明军, 赵喜杨, 姚兵. (2m+1,1)-p-树的二分强优美性和二分强奇优美性[J]. 应用数学学报, 2016, 39(3): 419-428. [4] 刘新求, 黄元秋. 一类循环图在射影平面上的嵌入[J]. 应用数学学报, 2015, 38(3): 385-395. [5] 唐晓清, 刘念祖, 王汉兴, 白延琴. 正则树的双变量色多项式研究[J]. 应用数学学报(英文版), 2013, 36(4): 761-768. [6] 侯丽霞, 左连翠. 龙虾树的多级距离标号[J]. 应用数学学报(英文版), 2011, 34(5): 838-852. [7] 管宇, 张晓东, 徐光辉. 树的变形与代数连通度[J]. 应用数学学报(英文版), 2011, 34(2): 341-352. [8] 管宇, 张晓东, 徐光辉. 树的变形与代数连通度[J]. 应用数学学报(英文版), 2011, 34(1): 341-352. [9] 刘新求, 黄元秋, 王晶. 多重圈梯图在射影平面上的嵌入个数[J]. 应用数学学报(英文版), 2010, 33(2): 317-327. [10] 祁忠斌, 张和平. 冠状系统的R-旋转图与-R-旋转图[J]. 应用数学学报(英文版), 2010, 33(2): 269-280. [11] 刘颖, 曾伟梁, 刘焕平. 关于q-树二次整子图和n阶加点q-树色多项式的注记[J]. 应用数学学报(英文版), 2010, 33(1): 78-87. [12] 万良霞. 一般梯图的亏格分布[J]. 应用数学学报(英文版), 2008, 31(5): 806-816. [13] 张莉. 树的剖分值[J]. 应用数学学报(英文版), 2008, 31(5): 852-860. [14] 邵泽玲、曹荣荣. 用联树法探讨图的最小亏格[J]. 应用数学学报(英文版), 2008, 31(5): 817-825. [15] 杨 \ \ 艳 郝荣霞. 扇图在曲面上嵌入的分类[J]. 应用数学学报(英文版), 2008, 31(5): 792-798. PDF全文下载地址: http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14258 相关话题/应用数学 控制 统计 华东师范大学 代数 领限时大额优惠券,享本站正版考研考试资料! 优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ... 考试优惠券 本站小编 Free壹佰分学习网 2022-09-19 给定团数的连通图的最小代数连通度 给定团数的连通图的最小代数连通度李建喜1,郭继明2,邵慰慈31.闽南师范大学数学与统计学院,漳州363000;2.华东理工大学理学院,上海200237;3.香港浸会大学数学系,香港,九龙塘TheMinimumAlgebraicConnectivityofGraphswithaGivenCliqueN ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 正则多部竞赛图的控制图 正则多部竞赛图的控制图李瑞娟,刘冬婷山西大学数学科学学院,太原030006TheDominationGraphofaRegularMultipartiteTournamentLIRuijuan,LIUDongtingSchoolofMathematicalSciences,ShanxiUnivers ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 参量离散代数oneRiccati方程centerline对称解的两类迭代算法 参量离散代数oneRiccati方程centerline对称解的两类迭代算法张凯院,耿小姣,聂玉峰西北工业大学应用数学系,西安710072Two-classIterativeAlgorithmsfortheSymmetricSolutionofDiscreteAlgebraicRiccatiEqua ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 具反馈控制的单方不能独立生存合作系统稳定性研究 具反馈控制的单方不能独立生存合作系统稳定性研究周晓燕1,普丽琼2,薛亚龙3,谢向东31.福州职业技术学院公共基础部,福州350108;2.福州大学数学与计算机科学学院,福州350108;3.宁德师范学院数学系,宁德352100OntheStabilityPropertyofanObligateLot ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 变分同伦摄动迭代法求解抛物型方程反问题中的控制参数 变分同伦摄动迭代法求解抛物型方程反问题中的控制参数白伟1,郭士民21.宁夏师范学院数学与计算机科学学院,宁夏756000;2.西安交通大学数学与统计学院,西安710049VariationalHomotopyPerturbationIterationMethodforComputingaContro ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 水体富营养化状态脉冲控制系统周期解的存在性和唯一性 水体富营养化状态脉冲控制系统周期解的存在性和唯一性孙树林,段晓祥山西师范大学数学与计算机科学学院,临汾041000ExistenceandUniquenessofPeriodicSolutionofaState-dependentImpulsiveControlSystemonWaterEutrop ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 基于指令滤波的异步电动机随机有限时间模糊自适应控制 马盼盼1,2，于金鹏1,2，刘加朋1,2，赵林1,2，于海生1,21.青岛大学自动化学院,青岛266071;2.山东省工业控制重点实验室,青岛266071出版日期:2021-11-25发布日期:2021-12-25StochasticFinite-TimeFuzzyAdaptiveControlfo ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 ``双循环''背景下医药制造业参与全球与国内价值链分工的统计研究 项莹，陈奇远浙江财经大学数据科学学院,杭州310018出版日期:2021-10-25发布日期:2021-12-24MeasurementofthePharmaceuticalManufacturingIndustry'sParticipationintheGlobalandDomesticValue ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 离散时间II型模糊双线性系统的耗散性控制 李琳，李江荣，毛晨斐延安大学数学与计算机科学学院,延安716000出版日期:2021-09-25发布日期:2021-11-25DesignofDissipativeControlforDiscrete-TimeIntervalType-2FuzzyBilinearSystemsLILinLI，Jia ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 在修正的~${\rmMin}(N,D)$-策略控制下延迟多级适应性休假~$M/G/1$~排队分析 罗乐1，唐应辉2，余玅妙2，吴文青31.南充职业技术学院,南充637000;2.四川师范大学数学科学学院,成都610068;3.西南科技大学理学院,绵阳621000出版日期:2021-09-25发布日期:2021-11-25AnalysisofM/G/1QueuewithDelayedMultipl ... 中科院数学与系统科学研究院 本站小编 Free考研考试 2021-12-27 Free考研考试FreeKaoYan.Com 欢迎来到Free考研考试，"为实现人生的Free而奋斗" 关于我们 联系我们 电子邮件 苏ICP备16059069号 © 2020 FreeKaoYan! . All rights reserved.