期刊文献+

求解区间图上的罗马控制数的动态规划算法 被引量:2

Dynamic programming algorithm to solve Roman domination number for interval graph
下载PDF
导出
摘要 针对区间图的最小罗马控制函数和罗马控制数求解的困难性,提出了一种动态规划算法。从区间图的顶点排序开始,结合区间图的某些性质,采用逐步搜索的方法,不断扩大搜索的顶点集合范围,最终求出最优的罗马控制集和罗马控制数。为保证算法的正确性和科学性,对算法进行了严格的数学推理和证明。最后还给出了一个典型的区间图求解过程的演示示例,增强了算法的可读性和可操作性。结果表明该算法不仅运算速度快,而且简单易行。 This paper proposed a dynamic programming algorithm to find a minimum Roman dominating function and Roman domination number for an interval graph. It designed a step by step search algorithm to solve this problem. Starting with a vertex ordering of an interval graph,combining with some properties of interval graphs,it successfully found the optimum Roman dominating function and Roman domination number. It presented a mathematical proof to ensure the correctness of the algorithm. Finally it took an example to illustrate the procedure of the described algorithm. The results show that the algorithm is fast and effective.
作者 杨洪 张修军 吴璞 李宏 Yang Hong;Zhang Xiujun;Wu Pu;Li Hong(School of Information Science & Engineering,Chengdu University,Chengdu 610106,China)
出处 《计算机应用研究》 CSCD 北大核心 2018年第7期1986-1988,共3页 Application Research of Computers
基金 国家自然科学基金资助项目(61309015) 成都市科技局软科学项目(2015-RK00-00202-ZF)
关键词 区间图 罗马控制函数 罗马控制数 权重 动态规划算法 interval graph Roman dominating function Roman domination number weight dynamic programming algorithm
  • 相关文献

参考文献2

二级参考文献11

  • 1S.W.Cheng,M.Kaminski,S.Zads.Minimum dominating sets of intervals on lines.Algorithmica,1998,20:294~308.
  • 2M.C.Golumbic.Algorithmic Graph Theory and Perfect Graphs,Academic Press,New York,1980.
  • 3E.McCreight.Priority search trees.SIAM J.Comput.,1985,14:257~276.
  • 4G.Ramalingam,P.Rangan.A unified approach to domination problems on interval graphs.Inform.Process.Lett.,1988,27:271~274.
  • 5A.Bertossi,A.Gori.Total domination and irredundance in weighted interval graphs.SIAM J.Discrete Math.,1988,3:317~327.
  • 6B.Bollobás.Modern Graph Theory[M].New York:Spring-Verlag,2001.
  • 7K.Booth,J.Johnson.Dominating sets in chordal graphs.SIAM J.Comput.,1982,11:191~199.
  • 8K.Booth,G.Leuker.Testing for consecutive ones property,interval graph,and graph planarity using PQ-tree algorithms.J.Comput.System Sci.1976,13:335~379.
  • 9A.Brandtstaedt.The computational complexity of feedback vertex set,hamiltonian circuit,dominating set,steinertree,and bandwidth on special perfect graphs.J.Inform.Process.Cybern.,1987,23:471~474.
  • 10M.S.Chang.Efficient algorithms for the domination problems on interval and circular-arc graphs,SIAM J.Comput.,1998,6:1671~1694.

共引文献3

同被引文献6

引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部