The forwarding index of directed networks (Q1923618)

In an \(n\)-node digraph, a routing is defined as a set of \(n(n-1)\) paths specified for all ordered pairs of nodes of the digraph, one path for each pair. The load of a node is the number of paths going through it. The forwarding index of the digraph is the minimum of the largest load taken over all routings. The paper gives upper bounds on the forwarding index in \(k\)-connected digraphs and in digraphs with half-degrees at least \(k\).