A Parallel Algorithm for Constructing Multiple Independent Spanning Trees in Bubble-Sort Networks

Shih Shun Kao, Ralf Klasing, Ling Ju Hung, Sun Yuan Hsieh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. [Journal of Combinatorial Optimization 38 (2019) 972–986] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks Bn and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O(n· n! ) of our algorithm is asymptotically optimal, where n is the dimension of Bn and n! is the number of vertices of the network.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
EditorsWeili Wu, Hongwei Du
PublisherSpringer Science and Business Media Deutschland GmbH
Pages252-264
Number of pages13
ISBN (Print)9783030931759
DOIs
Publication statusPublished - 2021
Event15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021 - Virtual, Online
Duration: 2021 Dec 202021 Dec 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13153 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
CityVirtual, Online
Period21-12-2021-12-22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A Parallel Algorithm for Constructing Multiple Independent Spanning Trees in Bubble-Sort Networks'. Together they form a unique fingerprint.

Cite this