کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436437 | 690003 | 2014 | 11 صفحه PDF | دانلود رایگان |
A Disjoint Path Cover (DPC for short) of a graph is a set of pairwise (internally) disjoint paths that altogether cover every vertex of the graph. Given a set S of k sources and a set T of k sinks, a many-to-many k-DPC between S and T is a disjoint path cover each of whose paths joins a pair of source and sink. It is classified as paired if each source of S must be joined to a designated sink of T, or unpaired if there is no such constraint. In this paper, we show that every m -dimensional restricted hypercube-like graph with at most m−3m−3 faulty vertices and/or edges being removed has a paired (and unpaired) 2-DPC joining arbitrary two sources and two sinks where m⩾5m⩾5. The bound m−3m−3 on the number of faults is optimal for both paired and unpaired types.
Journal: Theoretical Computer Science - Volume 531, 24 April 2014, Pages 26–36