   Next: 4.3 A faster algorithm Up: 4 Establishing many paths Previous: 4.1 Unshared neighbors

## 4.2 A level-by-level algorithm

Our first algorithm extends the paths from level 0 to level by first extending all the paths from level 0 to level 1, then from level 1 to level 2, and so on. As we shall see, extending the paths from one level to the next can be done in bit steps, so the total time is bit steps.

In a multibutterfly with the unshared-neighbors property, it is relatively easy to extend paths from one level to the next because paths at nodes with unshared neighbors can be extended without worrying about blocking any other paths that are trying to reach the next level. The remaining paths can then be extended recursively. In particular, all the paths can be extended from level l to level l+1 (for any l), by performing a series of ``steps'', where each step consists of: Note that each step can be implemented in a constant number of bit steps.

Since the splitters connecting level l to level l+1 have inputs, and at most paths must be extended to the upper (or lower) outputs, for , the number of inputs containing these paths is at most . Thus, we can apply the unshared-neighbors property to these nodes. As a consequence, in each step the number of paths still remaining to be extended decreases by a factor. After steps, no paths remain to be extended.

By using the path-extension algorithm just described to extend all of the paths from level 0 to level 1, then all of the paths from level 1 to level 2, and so on, we can construct all the paths in steps.

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