In this section we generalize the routing algorithm of Section 4 by removing the distinction between nodes that are terminals and nodes that are not. The algorithm in this section requires word steps, not bit steps. Recall that in the word model, each edge can transmit a word of bits in a single step. The goal of the algorithm is to establish a set of disjoint paths, each of which may start or end at any node in the network. The following similar problem was studied by Peleg and Upfal [27].
Given an expander graph, G, K source nodes, in G, and K sink nodes, in G, where the sources and sinks are all distinct (i.e., and for , and for all i and j), construct a path in G from each source to the corresponding sink , so that no two paths share an edge.Peleg and Upfal presented polylogarithmic time algorithms for finding K edge-disjoint paths in any n-node expander graph, provided that , where is a fixed constant less one. In this section we show that if we are allowed to specify the network (but not the locations of the sources and sinks) then it is possible to construct even more paths. In particular, we describe an n-node bounded-degree network, R, and show how to find K edge-disjoint paths in it in time, provided that . Furthermore, we show how to find node-disjoint paths between of the sources and sinks.