   Next: 5.3.2 Constructing node-disjoint paths Up: 5.3 Removing the distinction Previous: 5.3 Removing the distinction

### 5.3.1 The network

The network R consists of four parts, each of which contains levels of N nodes. Each of the first three parts shares its last level with the first level of the next part, so the total number of levels is , and the total number of nodes in the network is .

The first part is a set of levels labeled through . For , the edges connecting level i to i+1, form an N-input merger. Hence, every set of nodes on one level has at least neighbors on the next level, where , , and d are related as in Equation 2.2.

The second part consists of a multibutterfly whose levels are labeled through 0. The multibutterfly has expansion property , where , , and d are related as in Equation 2.1.

The third and fourth parts are the mirror images of the first and second parts. The levels of these parts are labeled 0 through .

Although any node in R can be chosen to be a source or a sink, it would be more convenient if all of the sources were to reside in the first part, and all the sinks in the fourth. Thus, the node on level -i of the second part, i of the third part, and of the fourth part each have an edge called a cross edge to the corresponding node on level of the first part. Similarly, each node in the fourth part has cross edges to the corresponding nodes in first, second, and third parts. If a node in any part other than the first is chosen to be a source, then its path begins with its cross edge to the first part. If a node in any part other than the fourth is chosen to be a sink, then the path to it ends with a cross edge from the fourth part. At this point, each node in the first part may represent up to four sources, and each node in the fourth part may represent up to four sinks.   Next: 5.3.2 Constructing node-disjoint paths Up: 5.3 Removing the distinction Previous: 5.3 Removing the distinction

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