单位区间图的半配对k-不相交路覆盖研究

doi:10.6040/j.issn.1671-9352.0.2022.404

摘要/Abstract

摘要：

研究单位区间图上的半配对多对多k-不相交路覆盖(k-disjoint path cover, k-DPC)的容错性问题, 利用路覆盖的结构特点, 结合单位区间图顶点序的结构性质, 刻画具有半配对1-DPC和k-DPC性质的单位区间图。同时得到单位区间图G任意删去点集W且任意经过边集F的相关结果: G-W且经过F具有半配对1-DPC性质当且仅当G是(2+r)-连通, 其中|W|=p, |F|=q, p+q≤r; G-W且经过F具有半配对k-DPC性质当且仅当G是(2k+r-1)-连通, 其中k≥2。结果表明: 图中不相交路覆盖的存在与顶点连通度和哈密顿性质密切相关。研究方法与结果为进一步研究区间图及其他相关图类的路覆盖问题提供理论依据。

关键词: 单位区间图, 半配对k-DPC, 容错性, 路覆盖

Abstract:

The fault tolerance problem of semi-paired, many to many and k-disjoint path cover (k-DPC) on unit interval graphs is studied. Using the structural characteristics of the path cover and the structural properties of the vertex order of the unit interval graphs, the unit interval graphs with semi-paired 1-DPC and k-DPC properties are characterized. At the same time, we obtain the relevant results of the unit interval graph G: for any vertex set W and any edge set F, G-W passing through F has the semi-paired 1-DPC property if and only if G is (2+r)-connected, where |W|=p, |F|=q, p+q≤r; G-W passing through F has the semi-paired k-DPC property if and only if G is (2k+r-1)-connected, where k≥2. It is shown that the existence of disjoint path covers in graphs is closely related to vertex connectivity and Hamiltonian properties. The research methods and results provide a theoretical basis for further study of the path coverage of interval graphs and other related graphs.

Key words: unit interval graph, semi-paired k-DPC, fault tolerance, path cover

中图分类号:

O157.5

朱莉,李鹏,王爱法. 单位区间图的半配对k-不相交路覆盖研究[J]. 《山东大学学报(理学版)》, 2024, 59(2): 80-90.

Li ZHU,Peng LI,Aifa WANG. Study on semi-paired k-disjoint path cover of unit interval graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 80-90.

图/表 23

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

图19

图20

图21

图22

图23

参考文献 24

1	WANG Fan , ZHAO Weisheng . One-to-one disjoint path covers in hypercubes with faulty edges[J]. The Journal of Supercomputing, 2019, 75 (8): 5583- 5595. doi: 10.1007/s11227-019-02817-6
2	DUSART J , CORNEIL D G , HABIB M . Corrigendum: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs[J]. SIAM Journal on Computing, 2021, 50 (3): 1148- 1153. doi: 10.1137/20M1327835
3	PARK J H , CHOI J , LIM H S . Algorithms for finding disjoint path covers in unit interval graphs[J]. Discrete Applied Mathematics, 2016, 205, 132- 149. doi: 10.1016/j.dam.2015.12.002
4	CHEN Xiaodong , LIU Mingda , LIU Huiqing . Minimum path cover in quasi-claw-free graphs[J]. Bulletin of the Iranian Mathematical Society, 2020, 46 (3): 815- 820. doi: 10.1007/s41980-019-00294-4
5	YU Wei , LIU Zhaohui . Better approximability results for min-max tree/cycle/path cover problems[J]. Journal of Combinatorial Optimization, 2019, 37 (2): 563- 578. doi: 10.1007/s10878-018-0268-8
6	GURSKI F , KOMANDER D , REHS C , et al. Computing directed Steiner path covers[J]. Journal of Combinatorial Optimization, 2022, 43 (2): 402- 431. doi: 10.1007/s10878-021-00781-7
7	LI Jing , WANG Guoren , CHEN Lichao . Paired 2-disjoint path covers of multi-dimensional torus networks with 2n-3 faulty edges[J]. Theoretical Computer Science, 2017, 677, 1- 11. doi: 10.1016/j.tcs.2017.03.008
8	LI J , MELEKIAN C , ZUO S R , et al. Unpaired many-to-many disjoint path covers on bipartite k-ary n-cube networks with faulty elements[J]. International Journal of Foundations of Computer Science, 2020, 31 (3): 371- 383. doi: 10.1142/S0129054120500148
9	PARK J H . Paired many-to-many 3-disjoint path covers in bipartite toroidal grids[J]. Journal of Computing Science and Engineering, 2018, 12 (3): 115- 126. doi: 10.5626/JCSE.2018.12.3.115
10	PARK J H , IHM I . A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph[J]. Information Processing Letters, 2019, 142 (2): 57- 63.
11	ĆUSTIĆ A , LENDL S . The Steiner cycle and path cover problem on interval graphs[J]. Journal of Combinatorial Optimization, 2022, 43 (1): 226- 234. doi: 10.1007/s10878-021-00757-7
12	CHEN Yong , CAI Yinhui , LIU Longcheng , et al. Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph[J]. Journal of Combinatorial Optimization, 2022, 43 (3): 571- 588. doi: 10.1007/s10878-021-00793-3
13	KAVRA R , GUPTA A , KANSAL S . Interval graph based energy efficient routing scheme for a connected topology in wireless sensor networks[J]. Wireless Networks, 2021, 27 (8): 5085- 5104. doi: 10.1007/s11276-021-02782-0
14	PATEL Y S , BAHETI A , MISRA R . Interval graph multi-coloring-based resource reservation for energy-efficient containerized cloud data centers[J]. The Journal of Supercomputing, 2021, 77 (5): 4484- 4532. doi: 10.1007/s11227-020-03439-z
15	AVANI V S , SHAILA S G , VADIVEL A . Interval graph of facial regions with common intersection salient points for identifying and classifying facial expression[J]. Multimedia Tools and Applications, 2021, 80 (3): 3367- 3390. doi: 10.1007/s11042-020-09806-5
16	LI Xingfu , FENG Haodi , JIANG Haotao , et al. Solving the maximum internal spanning tree problem on interval graphs in polynomial time[J]. Theoretical Computer Science, 2018, 734, 32- 37. doi: 10.1016/j.tcs.2017.09.017
17	PRADHAN D , PAL S . An O(n+m) time algorithm for computing a minimum semitotal dominating set in an interval graph[J]. Journal of Applied Mathematics and Computing, 2021, 66 (1): 733- 747.
18	KRATOCHVÍL J , MAS$\mathop {\rm{R}}\limits^{\smile}$ÍK T , NOVOTNÁ J . U-bubble model for mixed unit interval graphs and its applications: the maxcut problem revisited[J]. Algorithmica, 2021, 83 (12): 3649- 3680. doi: 10.1007/s00453-021-00837-4
19	PARK J H , KIM J H , LIM H S . Disjoint path covers joining prescribed source and sink sets in interval graphs[J]. Theoretical Computer Science, 2019, 776, 125- 137. doi: 10.1016/j.tcs.2019.01.019
20	PARK J H , LIM H S . Characterization of interval graphs that are unpaired 2-disjoint path coverable[J]. Theoretical Computer Science, 2020, 821, 71- 86. doi: 10.1016/j.tcs.2020.03.010
21	PARK J H . A sufficient condition for the unpaired k-disjoint path coverability of interval graphs[J]. The Journal of Supercomputing, 2021, 77 (7): 6871- 6888. doi: 10.1007/s11227-020-03512-7
22	LI Peng , WU Yaokun . A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs[J]. SIAM Journal on Discrete Mathematics, 2017, 31 (1): 210- 239. doi: 10.1137/140981265
23	LOOGES P J , OLARIU S . Optimal greedy algorithms for indifference graphs[J]. Computers & Mathematics with Applications, 1993, 25 (7): 15- 25.
24	CHEN C , CHANG C C , CHANG G J . Proper interval graphs and the guard problem[J]. Discrete Mathematics, 1997, 170 (1/2/3): 223- 230.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	袁军霞1,2,周厚春1*,许娟1. Macula分离矩阵的推广[J]. J4, 2012, 47(4): 97-100.
[2]	韩娜1,2,李慧娟1,2,刁科凤1*. 一类基于完全图K2m上匹配的相交关系的池设计[J]. J4, 2012, 47(12): 53-56.
[3]	雒金梅,左连翠*. 关于图的L(2,1)-标号的岛序列[J]. J4, 2011, 46(6): 49-52.