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

Shih Shun Kao, Kung Jui Pai, Sun-Yuan Hsieh, Ro Yu Wu, Jou Ming Chang

研究成果: Article

摘要

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(≠ 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 Sn and bubble-sort network Bn 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 Sn (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on Bn is not dealt with yet. In this paper, we present an algorithm to construct n- 1 ISTs of Bn. 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.

原文English
頁(從 - 到)972-986
頁數15
期刊Journal of Combinatorial Optimization
38
發行號3
DOIs
出版狀態Published - 2019 十月 15

指紋

Bubble sort
Cayley Graph
Spanning tree
Stars
Vertex of a graph
Star
Broadcasting
Telecommunication networks
Interconnection Networks
Time Constant
Fault-tolerant
Topology
Communication Networks
Defects
Path
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

引用此文

Kao, Shih Shun ; Pai, Kung Jui ; Hsieh, Sun-Yuan ; Wu, Ro Yu ; Chang, Jou Ming. / Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks. 於: Journal of Combinatorial Optimization. 2019 ; 卷 38, 編號 3. 頁 972-986.
@article{7b80ae3019514a91bbb332be64ead423,
title = "Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks",
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(≠ 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 Sn and bubble-sort network Bn 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 Sn (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on Bn is not dealt with yet. In this paper, we present an algorithm to construct n- 1 ISTs of Bn. 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.",
author = "Kao, {Shih Shun} and Pai, {Kung Jui} and Sun-Yuan Hsieh and Wu, {Ro Yu} and Chang, {Jou Ming}",
year = "2019",
month = "10",
day = "15",
doi = "10.1007/s10878-019-00430-0",
language = "English",
volume = "38",
pages = "972--986",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "3",

}

Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks. / Kao, Shih Shun; Pai, Kung Jui; Hsieh, Sun-Yuan; Wu, Ro Yu; Chang, Jou Ming.

於: Journal of Combinatorial Optimization, 卷 38, 編號 3, 15.10.2019, p. 972-986.

研究成果: Article

TY - JOUR

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

AU - Kao, Shih Shun

AU - Pai, Kung Jui

AU - Hsieh, Sun-Yuan

AU - Wu, Ro Yu

AU - Chang, Jou Ming

PY - 2019/10/15

Y1 - 2019/10/15

N2 - 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(≠ 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 Sn and bubble-sort network Bn 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 Sn (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on Bn is not dealt with yet. In this paper, we present an algorithm to construct n- 1 ISTs of Bn. 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.

AB - 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(≠ 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 Sn and bubble-sort network Bn 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 Sn (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on Bn is not dealt with yet. In this paper, we present an algorithm to construct n- 1 ISTs of Bn. 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.

UR - http://www.scopus.com/inward/record.url?scp=85067294316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067294316&partnerID=8YFLogxK

U2 - 10.1007/s10878-019-00430-0

DO - 10.1007/s10878-019-00430-0

M3 - Article

AN - SCOPUS:85067294316

VL - 38

SP - 972

EP - 986

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

ER -