Skip to main navigation Skip to search Skip to main content

Transmission in Butterfly Networks

  • Indra Rajasingh
  • , Paul Manuel
  • , N. Parthiban
  • , D. Azubha Jemilet*
  • , R. Sundara Rajan
  • *Corresponding author for this work
  • Vellore Institute of Technology
  • School of Computing Science and Engineering
  • School of Mathematical and Physical Sciences
  • University of Newcastle

Research output: Contribution to journal › Article › peer-review

21 Scopus citations

Abstract

Wiener index of a graph $G$ is defined as $W(G) = frac 12 sum {u,v in V(G)}} d-{{G}}(u,v)$. The Transmission index $T(u)$ of a vertex $u$ in a graph $G$ is defined as $T(u) = sum {{v in V}}d(u,v)$. The original technique for the computation of Wiener index was by brute-force method applying distance matrix. Later a new technique using convex partition was introduced and this convex partition method was shown to be more efficient than distance matrix method. However, this convex partition method is not universal. Some interesting architectures such as butterfly and mesh of trees do not induce convex partition. In this paper, we introduce another partition technique to accommodate larger classes of graphs which are not solved by convex partition method. This partition technique is called transmission partition method. It is different from distance matrix method and convex partition method. We show that this new technique significantly reduces the time complexity to compute the Wiener index to constant time for larger classes of graphs. We demonstrate the efficiency of this technique on butterfly networks by computing its Wiener index and its Transmission index in constant time.

Original languageEnglish
Pages (from-to)1174-1179
Number of pages6
JournalComputer Journal
Volume59
Issue number8
DOIs
StatePublished - 1 Aug 2016

Keywords

  • Wiener index
  • butterfly network
  • convex partition
  • routing
  • transmission of a graph
  • transmission partition

Fingerprint

Dive into the research topics of 'Transmission in Butterfly Networks'. Together they form a unique fingerprint.

Cite this