In this paper, the problem of routing messages along shortest paths in a network of processors without using complete routing tables is considered. The Boolean Routing model is proposed and it is shown that it provides optimal representations of all shortest routes on some specific network topologies (such as paths, rings, trees, hypercubes, different types of d-dimensional grids, complete graphs and complete bipartite graphs). Moreover, it is also shown that the model deals efficiently with graphs obtained by applying some types of graph compositions, thus resulting in very efficient routing schemes for some classes of networks with regular topology. This is done by considering different significant cost measures of the space efficiency of the schemes considered.

Flammini, M., Gambosi, G. (1997). On devising Boolean Routing Schemes. THEORETICAL COMPUTER SCIENCE, 186, 171-198 [http://dx.doi.org/10.1016/S0304-3975(97)86543-7].

On devising Boolean Routing Schemes

GAMBOSI, GIORGIO
1997-01-01

Abstract

In this paper, the problem of routing messages along shortest paths in a network of processors without using complete routing tables is considered. The Boolean Routing model is proposed and it is shown that it provides optimal representations of all shortest routes on some specific network topologies (such as paths, rings, trees, hypercubes, different types of d-dimensional grids, complete graphs and complete bipartite graphs). Moreover, it is also shown that the model deals efficiently with graphs obtained by applying some types of graph compositions, thus resulting in very efficient routing schemes for some classes of networks with regular topology. This is done by considering different significant cost measures of the space efficiency of the schemes considered.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - Informatica
English
Boolean functions; Mathematical models; Program processors; Topology; Boolean routing schemes; Parallel processing systems
Flammini, M., Gambosi, G. (1997). On devising Boolean Routing Schemes. THEORETICAL COMPUTER SCIENCE, 186, 171-198 [http://dx.doi.org/10.1016/S0304-3975(97)86543-7].
Flammini, M; Gambosi, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/43473
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 7
social impact