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.

Text
Proceedings_30th_Euromicro_International_Conference.pdf - Published Version
Restricted to Registered users only
Download (968kB) | Request a copy

Abstract

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: