| 单位区间图的配对k-DPC容错性问题 |
| |
| 引用本文： | 李鹏,朱莉,王爱法,尚建辉.单位区间图的配对k-DPC容错性问题[J].重庆师范大学学报(自然科学版),2023,40(2):8-17. |
| |
| 作者姓名： | 李鹏 朱莉 王爱法 尚建辉 |
| |
| 作者单位： | 重庆理工大学 理学院， 重庆 400054;上海交通大学 数学科学学院， 上海 200240 |
| |
| 基金项目： | 国家自然科学基金项目(No.11701059)；重庆市自然科学基金项目(No.cstc2020jcyj-msxmX0272)；重庆市教育委员会科学技术研究计划项目(No.KJQN202001130；No.KJQN202101130；No.KJQN202001107)；上海自然科学基金项目(No.20ZR1427200)；重庆理工大学研究生教育高质量发展行动计划（No.gzlcx20222080） |
| |
| 摘 要： | 【目的】为研究不相交路径覆盖问题，在单位区间图上探讨1-不相交路径可覆盖、2-不相交路径可覆盖、k-不相交路径可覆盖在删除顶点和经过指定边后仍保持DPC性质的结构。【方法】利用单位区间图的结构特点以及路覆盖的结构性质，结合数学归纳法和反证法来研究单位区间图的配对多对多k-DPC容错性问题。【结果】单位区间图G任意删去p个点且经过q条边，仍是配对k-DPC,当且仅当G是(2k+r-1)-连通，其中(p+q)≤r。【结论】单位区间图的容错性路覆盖问题与哈密顿性质以及连通度有紧密联系。研究方法和研究结果为区间图配对k-DPC容错性问题的研究提供了理论依据，同时有助于设计在单位区间图上寻找配对k-DPC容错性的有效算法。
|
| 关 键 词： | 路覆盖 配对k-不相交路径可覆盖 单位区间图 容错性 |
Research on Paired k-DPC Fault Tolerance of Unit Interval Graphs |
| |
| Institution: | College of Science, Chongqing University of Technology, Chongqing 400054; School of Mathematical Sciences, Shanghai Jiaotong University, Shanghai 200240, China |
| |
| Abstract: | |
| |
| Keywords: | path cover paired k-disjoint path coverable unit interval graph fault tolerance |
|
| 点击此处可从《重庆师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《重庆师范大学学报(自然科学版)》下载免费的PDF全文 |
