next up previous
Next: 5.3.1 The network Up: 5 Extensions Previous: 5.2 Multiple calls to

5.3 Removing the distinction between terminals and non-terminals

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 tex2html_wrap_inline2401 word steps, not bit steps. Recall that in the word model, each edge can transmit a word of tex2html_wrap_inline2403 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, tex2html_wrap_inline2409 in G, and K sink nodes, tex2html_wrap_inline2415 in G, where the sources and sinks are all distinct (i.e., tex2html_wrap_inline2419 and tex2html_wrap_inline2421 for tex2html_wrap_inline2423 , and tex2html_wrap_inline2425 for all i and j), construct a path in G from each source tex2html_wrap_inline2433 to the corresponding sink tex2html_wrap_inline2435 , 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 tex2html_wrap_inline2441 , where tex2html_wrap_inline2443 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 tex2html_wrap_inline2451 time, provided that tex2html_wrap_inline2453 . Furthermore, we show how to find node-disjoint paths between tex2html_wrap_inline2455 of the sources and sinks.

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996