Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Reliable and Efficient Fixed Rountings on Digraphs
IEICE TRANSACTIONS (1976-1990) Vol.E71 No.12 pp.1212-1220
Publication Date: 1988/12/20
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on CAS Karuizawa Workshop)
Full Text: PDF(666.4KB)
The problem of constructing a reliable and efficient routing ρ in a communications network G is considered. The forwarding index ξ(G, ρ), which is defined as the maximum number of routes which pass through each node, is a criterion of network efficiency. The diameter of the surviving route graph D(R(G, ρ)/F), which is defined as the maximum number of surviving routes needed for communication between each pair of nodes if node and edge faults F occur, is a criterion of network reliability. Routings which minimize ξ(G, ρ) and D(R(G, ρ)/F) are needed. In this paper the following are shown: (1) A sufficient condition for k-connected digraphs (k2, 4) to have a routing ρ such that D(R(G, ρ)/F)6 for |F|k. (2) A method of constructing a digraph G and routing ρ2 such that ξ(G, ρ2)2logdn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ2)3logdn and D(R(G, )/F)3 for |F|d-1 if nd4 and d3.