The forwarding diameter of graphs

✍ Scribed by W.Fernandez De La Vega; M. El Haddad; D. Barraez; O. Ordaz

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 641 KB
• Volume: 86
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00041-9

✦ Synopsis

A routing R in a graph G is a set of paths {RX,, : x, y E V(G)} where, for each ordered pair of vertices (x, y), RXy links x to y. The load <(G, R, x) of a vertex x in the routing R is the number of paths of R for which x is an interior vertex. We define the forwarding diameter p( G, R) of the pair (G, R) by

and the forwarding diameter /J(G) of G as the minimum of p(G, R) taken over all possible routings. In this paper, the introduction of the parameter p(G) is motivated by a natural model of message transmission in networks and we present several properties of p(G). In particular, we study the value of /J for several families of graphs such as the hypercube and the de Bruijn graphs and we also study the connection of p(G) with previously introduced transmission paramctcrs.