Optimum Interval Routing in k-Caterpillars and Maximal Outer Planar Networks.
Gur Saran Adhar · 2003
In this paper we present optimum interval routing algorithms for message passing networks that have topological structure defined by k-caterpillars and maximal outer planar graphs (MOPS). The routing algorithms are optimum in the sense that the route built between any source-destination pair is of minimum length and that the routing function executing at each node has time complexity which is linear in the size of the network.