Energy Initiative Energy Initiative
Office of the Provost
Duke University

 HOME > Provost > Energy Initiative    Search Help Login pdf version printable version 

Publications [#236681] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

  1. Aiello, WA; Leighton, FT; Maggs, BM; Newman, M, Fast algorithms for bit-serial routing on a hypercube, Mathematical Systems Theory, vol. 24 no. 1 (December, 1991), pp. 253-271, Springer Nature, ISSN 0025-5661 [doi]
    (last updated on 2024/03/28)

    Abstract:
    In this paper we describe an O(log N)-bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in an O(1)-dilated hypercube (i.e., the problem of establishing edge-disjoint paths between the nodes of the dilated hypercube for any one-to-one mapping). Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any randomized oblivious algorithm on a polylogarithmic degree network requires at least Ω(log2N/log log N) bit steps with high probability for almost all permutations. © 1991 Springer-Verlag New York Inc.


Duke University * Faculty * Staff * Reload * Login