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
AuthorsKlavž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.

Keywordsaverage distance; Wiener index; vertex-weighted graph; butterfly network; hypertree network
Year2016
JournalThe Computer Journal
Journal citation59 (12), pp. 1900-1910
PublisherOxford University Press
ISSN0010-4620
Digital Object Identifier (DOI)https://doi.org/10.1093/comjnl/bxw046
Scopus EID2-s2.0-85031321968
Page range1900-1910
FunderSlovenian Research Agency (ARRS)
Publisher's version
License
All rights reserved
File Access Level
Controlled
Output statusPublished
Publication dates
Online09 Dec 2016
Publication process dates
Accepted15 Jun 2016
Deposited29 Nov 2023
Permalink -

https://acuresearchbank.acu.edu.au/item/90028/average-distance-in-interconnection-networks-via-reduction-theorems-for-vertex-weighted-graphs

Restricted files

Publisher's version

  • 43
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month
These values are for the period from 19th October 2020, when this repository was created.

Export as

Related outputs

Zero forcing in iterated line digraphs
Ferrero, Daniela, Kalinowski, Thomas and Stephen, Sudeep. (2019). Zero forcing in iterated line digraphs. Discrete Applied Mathematics. 255, pp. 198-208. https://doi.org/10.1016/j.dam.2018.08.019
Minimum rank and zero forcing number for butterfly networks
Ferrero, Daniela, Grigorious, Cyriac, Kalinowski, Thomas, Ryan, Joe and Stephen, Sudeep. (2019). Minimum rank and zero forcing number for butterfly networks. Journal of Combinatorial Optimization. 37(3), pp. 970-988. https://doi.org/10.1007/s10878-018-0335-1
A lower bound on the zero forcing number
Davila, Randy, Kalinowski, Thomas and Stephen, Sudeep. (2018). A lower bound on the zero forcing number. Discrete Applied Mathematics. 250, pp. 363-367. https://doi.org/10.1016/j.dam.2018.04.015
Resolving-power dominating sets
Stephen, Sudeep, Rajan, Bharati, Grigorious, Cyriac and William, Albert. (2015). Resolving-power dominating sets. Applied Mathematics and Computation. 256, pp. 778-785. https://doi.org/10.1016/j.amc.2015.01.037
On the Strong Metric Dimension of Tetrahedral Diamond Lattice
Manuel, Paul, Rajan, Bharati, Grigorious, Cyriac and Stephen, Sudeep. (2015). On the Strong Metric Dimension of Tetrahedral Diamond Lattice. Mathematics in Computer Science. 9(2), pp. 201-208. https://doi.org/10.1007/s11786-015-0226-0
Power domination in certain chemical structures
Stephen, Sudeep, Rajan, Bharati, Ryan, Joe, Grigorious, Cyriac and William, Albert. (2015). Power domination in certain chemical structures. Journal of Discrete Algorithms (Amsterdam). 33, pp. 10-18. https://doi.org/10.1016/j.jda.2014.12.003
On the metric dimension of circulant and Harary graphs
Grigorious, Cyriac, Manuel, Paul, Miller, Mirka, Rajan, Bharati and Stephen, Sudeep. (2014). On the metric dimension of circulant and Harary graphs. Applied Mathematics and Computation. 248, pp. 47-54. https://doi.org/10.1016/j.amc.2014.09.045
On the partition dimension of a class of circulant graphs
Grigorious, Cyriac, Stephen, Sudeep, Rajan, Bharati, Miller, Mirka and William, Albert. (2014). On the partition dimension of a class of circulant graphs. Information Processing Letters. 114(7), pp. 353-356. https://doi.org/10.1016/j.ipl.2014.02.005