Improved bounds on the crossing number of butterfly network
Paul D. Manuel (1), Bharati Rajan (2) (3), Indra Rajasingh (4), P. Vasanthi Beulah (5)
(1) Department of Information Science [Kuwait]
(2) Department of Mathematics [Chennai]
(3) School of Electrical Engineering and Computer Science
(4) School of Advanced Sciences (SAS) [Chennai]
(5) Department of Mathematics - Queen Mary's College [Chennai]
Abstract
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.
