Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang

正确性 数学 反例 数学证明 支配集 区间(图论) 算法 组合数学 图形 集合(抽象数据类型) 离散数学 计算机科学 顶点(图论) 几何学 程序设计语言
作者
Toru Araki,Ryuya Saito
出处
期刊:Discrete Applied Mathematics [Elsevier BV]
卷期号:334: 139-144 被引量:2
标识
DOI:10.1016/j.dam.2023.04.002
摘要

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.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
DAYTOY完成签到 ,获得积分10
1秒前
这一天发布了新的文献求助10
1秒前
吴jun发布了新的文献求助10
1秒前
张婷发布了新的文献求助200
1秒前
weiwei完成签到,获得积分10
1秒前
uzi发布了新的文献求助10
1秒前
chenyu发布了新的文献求助10
2秒前
aajhajkahna应助元谷雪采纳,获得10
2秒前
ldz完成签到,获得积分10
2秒前
明明王应助LI采纳,获得10
2秒前
2秒前
hcy完成签到,获得积分10
2秒前
123完成签到,获得积分20
2秒前
lizishu完成签到,获得积分0
2秒前
赘婿应助科研通管家采纳,获得10
3秒前
领导范儿应助科研通管家采纳,获得10
3秒前
丘比特应助科研通管家采纳,获得10
3秒前
FashionBoy应助科研通管家采纳,获得10
3秒前
芈冖完成签到,获得积分10
3秒前
3秒前
3秒前
酷波er应助科研通管家采纳,获得10
3秒前
852应助科研通管家采纳,获得10
3秒前
万能图书馆应助科研通管家采纳,获得100
3秒前
华仔应助科研通管家采纳,获得10
3秒前
4秒前
4秒前
高大绝义完成签到,获得积分10
4秒前
nb完成签到,获得积分10
5秒前
herojine完成签到,获得积分10
5秒前
Wz完成签到 ,获得积分10
5秒前
兴奋灵发布了新的文献求助10
5秒前
哈基咪完成签到 ,获得积分10
5秒前
kbb发布了新的文献求助30
6秒前
xiaomihaoku完成签到,获得积分10
6秒前
6秒前
尔安发布了新的文献求助10
6秒前
Sivona完成签到,获得积分10
6秒前
6秒前
打打应助樊尔风采纳,获得10
7秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
Les Mantodea de Guyane: Insecta, Polyneoptera [The Mantids of French Guiana] 2500
Atlas of Aligner Treatment and Planning A Case-Based Approach 1000
Rocket Propulsion Elements, 10th Edition 800
悉尼大学博士学位论文,题目:Modelling and testing of one-sided stitched laminated composites. 作者:Kristopher P. Plain 700
Curating Socialism: A Handbook of International Art Exhibitions 1947-1989 530
Soil mites of the family Rhagidiidae (Actinedida: Eupodoidea). Morphology, Systematics, Ecology 520
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 工程类 有机化学 化学工程 生物化学 计算机科学 内科学 物理 复合材料 催化作用 细胞生物学 无机化学 光电子学 物理化学 电极 基因
热门帖子
关注 科研通微信公众号,转发送积分 7456952
求助须知:如何正确求助?哪些是违规求助? 9053306
关于积分的说明 19296825
捐赠科研通 7080112
什么是DOI,文献DOI怎么找? 3242925
关于科研通互助平台的介绍 2410633
邀请新用户注册赠送积分活动 2227463