Header menu link for other important links
X
A Self-stabilizing Minimum Average Stretch Spanning Tree Construction
S. Sengupta, , P.S. Anjana
Published in Springer Science and Business Media Deutschland GmbH
2022
Volume: 13464 LNCS
   
Pages: 119 - 135
Abstract
Stretch is a metric in the construction of spanning trees that measures the deviation in the distance between a pair of nodes in the tree compared to its shortest distance in the underlying graph. This paper proposes a silent self-stabilizing low stretch spanning tree construction protocol BuildTree, that is based on a Low Diameter Decomposition (LDD) technique. The LDD involves steps wherein the graph is decomposed into a small number of connected blocks or clusters, each having a low diameter value. The proposed BuildTree algorithm generates a spanning tree with an average stretch of nO ( 1 ) and converges to a correct configuration in O(n+ Δ· η) rounds, where n, Δ and η is the number of nodes in the graph, the maximum size of a cluster and the number of clusters, respectively. To the best of our knowledge, this is the first known work of using self-stabilization in order to make low stretch tree constructions fault-tolerant. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Science and Business Media Deutschland GmbH
ISSN03029743