next up previous
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 tex2html_wrap_inline1839 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 tex2html_wrap_inline1849 bit steps, so the total time is tex2html_wrap_inline1851 bit steps.

In a multibutterfly with the tex2html_wrap_inline1853 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 tex2html_wrap_inline1869 inputs, and at most tex2html_wrap_inline1871 paths must be extended to the upper (or lower) outputs, for tex2html_wrap_inline1873 , the number of inputs containing these paths is at most tex2html_wrap_inline1875 . Thus, we can apply the tex2html_wrap_inline1877 unshared-neighbors property to these nodes. As a consequence, in each step the number of paths still remaining to be extended decreases by a tex2html_wrap_inline1879 factor. After tex2html_wrap_inline1881 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



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