Space-efficient and fault-tolerant message routing in outerplanar networks
Greg N. Frederickson, Ravi Janardan · IEEE Transactions on Computers · 1988
The problem of designing space- and communication-efficient routing schemes for networks that experience faults is addressed. For any outerplanar network containing t faults, a succinct routing scheme is presented that uses O( alpha tn) space and communication to generate routings that are less than (( alpha +1)/( alpha -1))/sup t/ times longer than optimal, where alpha >1 is an odd-valued integer parameter. Thus, the routings can be tuned as desired, using a suitable amount of information. Efficient sequential and distributed algorithms are presented for setting up the routing schemes.>