ON DEVISING BOOLEAN ROUTING SCHEMES

In this paper, the problem of routing messages along shortest paths in a network of processors without using complete routing tables is cons idered. The Boolean Routing model is proposed and it is shown that it provides optimal representations of all shortest routes on some specif ic network topologies (such as paths, rings, trees, hypercubes, differ ent types of d-dimensional grids, complete graphs and complete biparti te graphs). Moreover, it is also shown that the model deals efficientl y with graphs obtained by applying some types of graph compositions, t hus resulting in very efficient routing schemes for some classes of ne tworks with regular topology. This is done by considering different si gnificant cost measures of the space efficiency of the schemes conside red.