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

dmtcs:611 - Discrete Mathematics & Theoretical Computer Science, May 18, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.611
Improved bounds on the crossing number of butterfly networkArticle

Authors: 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]

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.

https://doi.org/10.46298/dmtcs.611
Source: HAL:hal-00980758v1
Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: May 18, 2013
Accepted on: June 9, 2015
Submitted on: January 28, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 443 times.
This article's PDF has been downloaded 607 times.