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.

Mon Jul 22 21:19:59 EDT 1996