A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph

被引：6

作者：

Park, Jung-Heum ^{[1
]}

Ihm, Insung ^{[2
]}

机构：

[1] Catholic Univ Korea, Sch Comp Sci & Informat Engn, Seoul, South Korea

[2] Sogang Univ, Dept Comp Sci & Engn, Seoul, South Korea

来源：

INFORMATION PROCESSING LETTERS | 2019年 / 142卷

基金：

新加坡国家研究基金会;

关键词：

Disjoint path cover; Cube of graph; Graph algorithms; NETWORKS; ROOTS;

D O I：

10.1016/j.ipl.2018.10.010

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given two disjoint vertex sets S = {s} and T = {t(1), t(2), t(3)} of a connected graph, a one-to many 3-disjoint path cover joining s and T is a vertex-disjoint path cover {P-1, P-2, P-3} such that each path P1 joins s and ti. In this paper, we present an efficient algorithm that builds, if exists, a one-to-many 3-disjoint path cover in the cube of a connected graph G joining the two terminal sets. Interestingly enough, we show that a carefully selected spanning tree or spanning unicyclic subgraph of G is all we need to find the desired disjoint path cover in time linear to the size of G. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：57 / 63

页数：7

共 16 条

[1] The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs [J].