A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph

作者：Ihm Insung; Park Jung Heum^*

来源：Discrete Applied Mathematics, 2017, 218: 98-112.

DOI：10.1016/j.dam.2016.10.027

• Disjoint path cover
• Cube of graph
• Hamiltonian path
• Spanning tree
• Unicyclic graph
• Linear-time algorithm

For a connected graph G = (V (G), E(G)) and two disjoint subsets of V(G)A = (alpha(1), ..., alpha(k)} and B = {beta(1,) ..., beta(k)}, a paired (many-to-many) k-disjoint path cover of G joining A and B is a vertex-disjoint path cover (beta(1), ..., beta(k)} such that P-i is a path from alpha(i) to beta(i) for 1 <= i <= k. In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 2-disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O vertical bar V(G)vertical bar + vertical bar E(G)vertical bar)-time algorithm that actually finds such a paired 2-disjoint path cover. In particular, we show that, in order to build a desired disjoint path cover, it is sufficient to consider only the edges of a carefully selected spanning tree of the graph and at most one additional edge not in the tree, which allows an efficient linear-time algorithm.

• 出版日期2017-2-19