求解区间图上的罗马控制数的动态规划算法

摘 要: 针对区间图的最小罗马控制函数和罗马控制数求解的困难性，本文提出了一个动态规划算法。从区间图的顶点排序开始，结合区间图的某些性质，采用逐步搜索的方法，不断扩大搜索的顶点集合范围，最终求出最优的罗马控制集和罗马控制数。为保证算法的正确性和科学性，对算法进行了严格的数学推理和证明。最后还给出了一个典型的区间图求解过程的演示示例，增强了算法的可读性和可操作性。结果表明该算法不仅运算速度快，而且简单易行。 关键词: 区间图；罗马控制函数；罗马控制数；权重；动态规划算法

A Dynamic Programming Algorithm to Solve Roman Domination Number for Interval Graph

Abstract: This paper proposed a dynamic programming algorithm to find a minimum Roman dominating function and Roman domination number for an interval graph. We 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, we successfully found the optimum Roman dominating function and Roman domination number. We presented a mathematical proof to ensure the correctness of the algorithm. Finally we took an example to illustrate the procedure of the described algorithm. The results show that the algorithm is fast and effective. Key words: interval graph; Roman dominating function; Roman domination number; weight; dynamic programming algorithm