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,Peleg and Upfal presented polylogarithmic time algorithms for findingG,Ksourcenodes, inG, andKsinknodes, inG, where the sources and sinks are all distinct (i.e., and for , and for alliandj), construct a path inGfrom each source to the corresponding sink , so that no two paths share an edge.

Mon Jul 22 21:19:59 EDT 1996