A Heuristic for Constructing Minimum Average Stretch Spanning Tree Using Betweenness Centrality

Sengupta, Sinchan and Peri, Sathya and Aggarwal, Vipul and Gupta, Ambey Kumari (2022) A Heuristic for Constructing Minimum Average Stretch Spanning Tree Using Betweenness Centrality. In: 30th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2022, 9 March 2022 through 11 March 2022, Valladolid.

[img] Text
Proceedings_30th_Euromicro_International_Conference.pdf - Published Version
Restricted to Registered users only

Download (968kB) | Request a copy


A parameter crucial for preserving the underlying shortest path information in spanning tree construction is called stretch. It is the ratio of the distance of two nodes x and y in the spanning tree to the shortest distance between x and y in the graph. In this paper, we present a heuristic LSTree that constructs a Minimum Average Stretch Spanning Tree of an n-node undirected and unweighted graph in \mathcal{O}(n) rounds of the CONGEST model. We like to stress that LSTree protocol is the first use of Betweenness centrality in the construction of low stretch trees. The heuristic outperforms the current benchmark algorithm of Alon et. al. as well as other spanning tree construction techniques presently known, when tested against synthetic as well as real-world graph inputs. © 2022 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Edge Betweenness Centrality; Graph; Min Stretch; Spanning Tree; Stretch Factor
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 20 Jul 2022 07:18
Last Modified: 20 Jul 2022 07:18
URI: http://raiith.iith.ac.in/id/eprint/9800
Publisher URL: http://doi.org/10.1109/PDP55904.2022.00019
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9800 Statistics for this ePrint Item