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

详细信息    查看全文

• 作者：Insung Ihm^a ; ^{ihm@sogang.ac.kr} ; Jung-Heum Park^b ; ^{j.h.park@catholic.ac.kr}
• 关键词：Disjoint path cover ; Cube of graph ; Hamiltonian path ; Spanning tree ; Unicyclic graph ; Linear-time algorithm
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：19 February 2017
• 年：2017
• 卷：218
• 期：Complete
• 页码：98-112
• 全文大小：1011 K
• 卷排序：218

文摘

For a connected graph G=(V(G),E(G))G=(V(G),E(G)) and two disjoint subsets of V(G)V(G) A={α1,…,αk}A={α1,…,αk} and B={β1,…,βk}B={β1,…,βk}, a paired (many-to-many) kk-disjoint path cover of GG joining AA and BB is a vertex-disjoint path cover {P1,…,Pk}{P1,…,Pk} such that PiPi is a path from αiαi to βiβi for 1≤i≤k1≤i≤k. In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 22-disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O(|V(G)|+|E(G)|)O(|V(G)|+|E(G)|)-time algorithm that actually finds such a paired 22-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.