Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements

A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpair...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2009-04, Vol.58 (4), p.528-540
Main Authors: Park, Jung-Heum, Kim, Hee-Chul, Lim, Hyeong-Seok
Format: Article
Language:English
Subjects:
Bipartite graph
Computer science
Construction industry
disjoint path covers
Educational institutions
Electronic mail
fault Hamiltonicity
Fault tolerance
interconnection networks
Joining processes
Multiprocessor interconnection
recursive circulants
restricted HL-graphs
strong Hamiltonicity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H 0 oplus H 1 obtained from connecting two graphs H 0 and H 1 with |V(H 0 )| = |V(H 1 )| by |V(H 1 )| pairwise nonadjacent edges joining vertices in H 0 and vertices in H 1 , where H 0 = G 0 oplus G 1 and H 1 = G 2 oplus G 3 for some graphs G j . Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2 m , 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2008.160