Fault-Tolerant Embedding of Longest Paths in Star Graphs with Edge Faults
Date Issued
1999-12-07
Date
1999-12-07
Author(s)
DOI
20060927122918898556
Abstract
In this paper, we aim to embed a longest path between every two vertices of a star graph with at most n-3
random edge faults, where n is the dimension of the star graph. Since the star graph is regular of degree n-1,
n-3 (edge faults) is maximum in the worst case. We show that when n摯瑬敳獩 6 and there are n-3 edge faults,
the star graph can embed a longest path between every two vertices, exclusive of two exceptions in which
there are at most two vertices missing from the longest path. The probabilities of the two exceptions are
analyzed. When n摯瑬敳獩 6 and there are n-4 edge faults, the star graph can embed a longest path between every
two vertices. The situation of n<6 is also discussed.
Subjects
embedding
fault-tolerant embedding
hamiltonian path
longest path
star graph
Publisher
臺北市:國立臺灣大學資訊工程學系
Type
report
File(s)![Thumbnail Image]()
Loading...
Name
star-99-04.pdf
Size
266.81 KB
Format
Adobe PDF
Checksum
(MD5):e022485b7354069d64edfbee18f44a08