Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang
Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang
复制标题
DOI：
10.1016/j.dam.2023.04.002
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Toru Araki;Ryuya Saito
中科院分区：
文献类型：
--
作者：
Toru Araki;Ryuya Saito
邹等人（2019）提出了一种计算固有区间图最小安全支配集的算法。然而，我们发现了一个反例，该算法输出了一个不正确的顶点子集。本文给出了一种改进的算法，并证明了算法的正确性。
Zou et al. (2019) proposed an algorithm for calculating a minimum secure dominating set of a proper interval graph. However, we find a counterexample for which the algorithm outputs an incorrect subset of vertices. In this paper, we provide a modified algorithm and the proofs for the correctness.