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 if 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.
展开▼
