Average distance in interconnection networks via reduction theorems for vertex-weighted graphs
Journal article
Klavžar, Sandi, Manuel, Paul, Nadjafi-Arani, M. J., Rajan, R. Sundara, Grigorious, Cyriac and Stephen, Sudeep. (2016). Average distance in interconnection networks via reduction theorems for vertex-weighted graphs. The Computer Journal. 59(12), pp. 1900-1910. https://doi.org/10.1093/comjnl/bxw046
Authors | Klavžar, Sandi, Manuel, Paul, Nadjafi-Arani, M. J., Rajan, R. Sundara, Grigorious, Cyriac and Stephen, Sudeep |
---|---|
Abstract | Average distance is an important parameter for measuring the communication cost of computer networks. A popular approach for its computation is to first partition the edge set of a network into convex components using the transitive closure of the Djoković–Winkler's relation and then to compute the average distance from the respective invariants of the components. In this article, we refine this idea further by shrinking the quotient graphs into smaller weighted graph called reduced graph, so that the average distance of the original graph is obtained from the reduced graphs. We demonstrate the significance of this technique by computing the average distance of butterfly and hypertree architectures. Along the way, a computational error from Klavžar and Nadjafi-Arani ((2014) Wiener index in weighted graphs via unification of Θ*-classes, Eur. J. Combin. 36, 71–76) is corrected. |
Keywords | average distance; Wiener index; vertex-weighted graph; butterfly network; hypertree network |
Year | 2016 |
Journal | The Computer Journal |
Journal citation | 59 (12), pp. 1900-1910 |
Publisher | Oxford University Press |
ISSN | 0010-4620 |
Digital Object Identifier (DOI) | https://doi.org/10.1093/comjnl/bxw046 |
Scopus EID | 2-s2.0-85031321968 |
Page range | 1900-1910 |
Funder | Slovenian Research Agency (ARRS) |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 09 Dec 2016 |
Publication process dates | |
Accepted | 15 Jun 2016 |
Deposited | 29 Nov 2023 |
https://acuresearchbank.acu.edu.au/item/90028/average-distance-in-interconnection-networks-via-reduction-theorems-for-vertex-weighted-graphs
Restricted files
Publisher's version
47
total views0
total downloads1
views this month0
downloads this month