Discrete Mathematics & Theoretical Computer Science, Vol 15, No 2 (2013)

Font Size:  Small  Medium  Large

Improved Bounds on the Crossing Number of Butterfly Network

Paul D. Manuel, Bharati Rajan, Indra Rajasingh, P. Vasanthi Beulah


We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.

Full Text: PDF PostScript