Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks

Shih-Shun Kao, Kung-Jui Pai, Sun-Yuan Hsieh, Ro-Yu Wu and Jou-Ming Chang ()
Additional contact information
Shih-Shun Kao: National Cheng Kung University
Kung-Jui Pai: Ming Chi University of Technology
Sun-Yuan Hsieh: National Cheng Kung University
Ro-Yu Wu: Lunghwa University of Science and Technology
Jou-Ming Chang: National Taipei University of Business

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 18, 972-986

Abstract: Abstract A set of spanning trees in a graph G is called independent spanning trees (ISTs for short) if they are rooted at the same vertex, say r, and for each vertex $$v(\ne r)$$ v ( ≠ r ) in G, the two paths from v to r in any two trees share no common edge and no common vertex except for v and r. Constructing ISTs has applications on fault-tolerant broadcasting and secure message distribution in reliable communication networks. Since Cayley graphs have been used extensively to design the topologies of interconnection networks, construction of ISTs on Cayley graphs is significative. It is well-known that star networks $$S_n$$ S n and bubble-sort network $$B_n$$ B n are two of the most attractive subclasses of Cayley graphs. Although it has been dealt with about two decades for the construction of ISTs on $$S_n$$ S n (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on $$B_n$$ B n is not dealt with yet. In this paper, we present an algorithm to construct $$n-1$$ n - 1 ISTs of $$B_n$$ B n . Moreover, we show that our algorithm has amortized efficiency for multiple trees construction. In particular, every vertex can determine its parent in each spanning tree in a constant amortized time. Accordingly, except for the star networks, it seems that our work is the latest breakthrough on the problem of ISTs for all subfamilies of Cayley graphs.

Keywords: Independent spanning trees; Bubble-sort networks; Interconnection networks; Multiple spanning trees protocol; Amortized analysis (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00430-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00430-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00430-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().