Manuel, Paul D. and Rajan, Bharati and Rajasingh, Indra and Beulah, P. Vasanthi - Improved bounds on the crossing number of butterfly network

dmtcs:611 - Discrete Mathematics & Theoretical Computer Science, May 18, 2013, Vol. 15 no. 2
Improved bounds on the crossing number of butterfly network

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

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.


Source : oai:HAL:hal-00980758v1
Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: May 18, 2013
Submitted on: January 28, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 47 times.
This article's PDF has been downloaded 91 times.