Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951205 | Journal of Computer and System Sciences | 2017 | 24 Pages |
Abstract
A disjoint path cover of a graph is a set of pairwise vertex-disjoint paths that altogether cover every vertex of the graph. In this paper, we prove that given k sources, s1, â¦, sk, in an m-dimensional restricted hypercube-like graph with a set F of faults (vertices and/or edges), associated with k positive integers, l1, â¦, lk, whose sum is equal to the number of fault-free vertices, there exists a disjoint path cover composed of k fault-free paths, each of whose paths starts at si and contains li vertices for iâ{1,â¦,k}, provided |F|+kâ¤mâ1. The bound, mâ1, on |F|+k is the best possible.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jung-Heum Park, Hee-Chul Kim, Hyeong-Seok Lim,