|
Published Articles >> Table of Contents >> Abstract
Fifth Asian Test Symposium (ATS'96)
p. 123
Constructing an Edge-Route Guaranteed Optimal Fault-Tolerant Routing for Biconnected Graphs
Yupin Luo, Tsinghua University
Shiyuan Yang, Tsinghua University
Dongcheng Hu, Tsinghua University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ATS.1996.555148
Send link to a friend
| Abstract |
|
Consider a graph that corresponds to a communication network in which a limited number of edge and/or node faults might occur. A routing for the network (a fixed path between each pair of nodes) must be chosen without knowing which components might become faulty. The diameter of a surviving route graph, where two nonfaulty nodes are connected by an edge iff there are no faults on the route between them, is considered to be one of the fault-tolerance measures for the routing. In this paper, we show that we can construct a routing for any biconnected graph and an arbitrary fault such that the diameter of its surviving route graph is not greater than two and unlike optimal routings constructed by the previous algorithm, our routing is also provided with the expected feature to routings that every edge is guaranteed to be chosen as the route between its two endpoints.
|
 Additional Information
|
Index Terms- Network, Fault tolerance, Routing, Diameter, Distributed computing
Citation:
Yupin Luo, Shiyuan Yang, Dongcheng Hu,
"Constructing an Edge-Route Guaranteed Optimal Fault-Tolerant Routing for Biconnected Graphs,"
ats,
p. 123,
Fifth Asian Test Symposium (ATS'96),
1996
|
|
