The forwarding diameter of graphs
A routing \(R\) in a graph \(G\) is a set of paths \(\{ R_{xy}: x,y \in V(G)\), \(x \not=y\}\) where, for the ordered pair of vertices \((x,y)\), \(R_{xy}\) is a path from \(x\) to \(y\). The load \(\xi (G,R,x)\) of a vertex \(x\) in the routing \(R\) is the number of paths in \(R\) for which \(x\) is an interior vertex. In an earlier paper of Chung et al., \(\xi\) was used to define a measure called the vertex-forwarding index of \(G\). An allied concept is the following: Let \(\mu (G,R) = \max_{x,y \in V(G)} \sum _{z \in V(R_{xy})-\{ x, y \} } \xi (G,R,z)\). The forwarding diameter of \(G\), \(\mu (G)\), is defined as the minimum of \(\mu (G,R)\) over all possible \(R\). The authors employ the theory of queuing networks to explain why \(\mu\) is more suitable than \(\xi\) to handle cases where the object is to minimize the maximum message transmission delay. Bounds for this new index are computed for the cycle, the wheel, the hypercube and the de Bruijn graphs.
- scientific article; zbMATH DE number 3761395 (Why is no real title available?)
- On forwarding indices of networks
- Queueing Networks: A Survey of Their Random Processes
- The forwarding index of communication networks
- The forwarding index of communication networks with given connectivity
- Upper bounds for the forwarding indices of communication networks
- Expanding and forwarding parameters of product graphs
- Expanding and forwarding
- The forwarding index of communication networks
- The forwarding index of the circulant networks
- The Forwarding Indices of Random Graphs
- Computation of the forwarding index via flows: A note
- scientific article; zbMATH DE number 1034100 (Why is no real title available?)
- Forwarding indices and bisection width of Sierpiński graphs
This page was built for publication: The forwarding diameter of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1270820)
