Boolean Routing on Chordal Rings
Danny Kriz̧anc, Flaminia L. Luccio · 1995
. In this paper we consider the problem of routing messages in a network of processors configured as a chordal ring. In particular we refer to the Boolean Routing model, and we introduce a new routing function for unidirectional and bidirectional chordal rings with degree four. This function requires O(n log n) bits of storage and O(n) time to compute, in the worst case. We also study some relations between our technique and Interval Routing Schemes. 1 Introduction Solving a routing problem consists of defining a way in which entities that are physically separated can communicate. If the two entities that want to communicate are directly connected, the routing is straightforward, since the message is sent on the edge that connects the two. If the two entities are not directly connected a path between them has to be found. We model the network with a connected graph G = (V; E) where V is the set of the nodes, jV j = n, and E is the set of edges. For each node i, i = 1; : : : ; n, d i ...