臺灣博碩士論文加值系統

在圖G上生成樹的集合如果他們有相同的點r當樹根，且圖G上每個點v(≠ r) 走到r的路徑再任意兩棵樹上都沒有共同的邊除了v和r ，則稱為獨立生成樹。在可靠的通訊網路中建構獨立生成樹可以應用於容錯廣播和安全訊息分散。由於Cayley 圖被廣泛用於設計連結網絡，所以在Cayley 圖上建構獨立生成樹的研究是非常有意義的。知名的星狀Sn 和氣泡排序Bn 網路是兩個最有吸引力的Cayley 子圖。儘管在Sn 上建構獨立生成樹已經過了大約二十年的時間，但迄今為止還沒有解決在Bn 建構獨立生成樹的問題。本篇論文中，我們指出在[Inform. Sci. 137 (2001) 259-276] Rescigno 的演算法有一些瑕疵，導致由此演算法所建構出的生成樹彼此之間可能不是點互斥的，於是我們呈現了一個修正的在Sn建構n - 1 獨立生成樹的方案。此外，在修正的方案基於獨立生成樹建造正確路徑的反向規則，我們提出一個新的演算法在Sn 建構n - 1 獨立生成樹。特別是這個提出的演算法是更有效率且可以容易的被應用在平行處理。我們也呈現了一個有效率的在Bn 建構n - 1 獨立生成樹的演算法，我們的成果是Cayley 圖的所有子圖除星狀網路之外獨立生成樹問題的最新突破。

A set of spanning trees in a graph G is called ndependent 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, say P1 and P2, satisfy E(P1) ∩ E(P2) = ∅ and V (P1) ∩ V (P2) = {v,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 interconnection networks, the study of constructing ISTs on Cayley graphs is very signicative. It is well-known that star networks Sn and bubble-sort network Bn are two of the most attractive subclasses of Cayley graphs. Accordingly, Rescigno in [Inform. Sci. 137 (2001) 259-276] proposed an algorithm to construct n - 1 ISTs rooted at a common vertex in an n-dimensional star network Sn. In this thesis, we first point out that there exists a flaw in Rescigno's algorithm, and thus the spanning trees constructed by this algorithm may not be ISTs. Then, a correct scheme for constructing n-1 ISTs on Sn is presented. Moreover, based on the reversing rule of building certain paths of ISTs in the amendatory scheme, we propose a new algorithm to construct n - 1 ISTs on Sn. In particular, the proposed algorithm is more ecient and can easily be implemented in parallel. Similarly, for n-dimensional bubble-sort network Bn, we also present an efficent algorithm to construct n - 1 ISTs. It seems that the latter result is the latest breakthrough on the problem of ISTs for all subclasses of Cayley graphs except star networks that mentioned above.

摘要I
Abstract II
誌謝III
Contents IV
List of Tables VI
List of Figures VIII
1 Introduction 1
2 Preliminaries 4
2.1 Interconnection networks . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The Star graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 The Bubble Sort graphs . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 ISTs on Star graphs 10
3.1 Rescigno's algorithm for constructing ISTs of Sn . . . . . . . . . . . . 10
3.2 An amendatory scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 13
IV
3.3 A fully parallelized algorithm for constructing ISTs of Sn . . . . . . . 18
4 ISTs on Star Bubble Sort graphs 23
4.1 Construction of ISTs . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Conclusions and Future Works 33
5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Bibliography 36

[1] S.B. Akers, B. Krishnamurty, A group theoretic model for symmetric intercon-
nection networks, IEEE Trans. Comput., 38 (1989) 555–566.
[2] S.B. Akers, D. Harel, B. Krishnamurty, The star graph: an attractive alter-
native to the n-cube, in: Proc. of the International Conference on Parallel
Processing, ICPP’87, University Park, August 1987, pp. 393–400.
[3] T. Araki, Y. Kikuchi, Hamiltonian laceability of bubble-sort graphs with edge
faults. Inform. Sci., 177 (2007) 2679–2691.
[4] S.G. Akl, K. Qiu, I. Stojmenovic, Fundamental algorithms for the star and
pancake interconnection networks with applications to computational geometry,
Networks, 23 (1993) 215-226.
[5] S.G. Akl, T. Wol, Ecient sorting on the star graph interconnection network,
Telcom. Syst., 10 (1998) 3-20.
[6] F. Bao, Y. Funyu, Y. Hamada, Y. Igarashi, Reliable broadcasting and secure
distributing in channel networks, in: Proc. of 3rd International Symposium on
Parallel Architectures, Algorithms and Networks, ISPAN'97, Taipei, December
1997, pp. 472-478.
[7] Y.-H. Chang, J,-S. Yang, S.-Y. Hsieh, J.-M. Chang, Y.-L. Wang, Construction
independent spanning trees on locally twisted cubes in parallel, J. Comb.
Optim., 33 (2017) 956-967.
[8] J.-M. Chang, T.-J. Yang, J.-S. Yang, A parallel algorithm for constructing
independent spanning trees in twisted cubes, Discrete Appl. Math., 219 (2017)
74-82.
[9] C.-C. Chen, J. Chen, Optimal parallel routing in star networks, IEEE Trans.
Comput., 46 (1997) 1293-1303.
[10] J. Cheriyan and S.N. Maheshwari, Finding nonseparating induced cycles and
independent spanning trees in 3-connected graphs, J. Algorithms, 9 (1988) 507-
537.
[11] S. Curran, O. Lee and X. Yu, Finding four independent trees, SIAM J. Comput.,
35 (2006) 1023-1058.
[12] K. Day, A. Tripathi, A comparative study of topologies properties of hypercubes
and star networks, IEEE Trans. Parallel Distrib. Syst., 5 (1994) 31-38.
[13] P. Fragopoulou, S.G. Akl, A parallel algorithm for computing Fourier transforms
on the star graph, IEEE Trans. Parallel Distrib. Syst., 5 (1994) 525-531.
[14] P. Fragopoulou, S.G. Akl, Optimal communication algorithms on star graphs
using spanning tree constructions, J. Parallel Distrib. Comput., 24 (1995) 55-
71.
[15] P. Fragopoulou, S.G. Akl, Edge-disjoint spanning trees on the star network
with applications to fault tolerance, IEEE Trans. Comput., 45 (1996) 174-185.
[16] T. Hasunuma, H. Nagamochi, Independent spanning trees with small depths in
iterated line digraphs, Discrete Appl. Math., 110 (2001) 189-211.
[17] R.-X. Hao, Z.-X. Tian, J.-M. Xu, Relationship between conditional diagnosability
and 2-extra connectivity of symmetric graphs, Theoret. Comput. Sci.,
627 (2012) 36-53.
[18] A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks,
Inform. Comput., 79 (1988) 43-59.
[19] Y. Kikuchi, T. Araki, Edge-bipancyclicity and edge-fault-tolerant bipancyclicity
of bubble-sort graphs, Inform. Process. Lett., 100 (2006) 52-59.
[20] S.-S. Kao, J.-M. Chang, K.-J. Pai, J.-S. Yang, S.-M. Tang, R.-Y. Wu, A parallel
construction of vertex-disjoint spanning trees with optimal heights in star
networks, Proc. 11th Int'l Conference on Combinatorial Optimization and Ap-
plications (COCOA 2017), Shanghai, Dec. 16-18, LNCS vol. 10627, pp. 472-478,
2017.
[21] S.-S. Kao, J.-M. Chang, K.-J. Pai, R.-Y. Wu, Constructing Independent Spanning
Trees on Bubble-Sort Networks, Proc. 24th Int'l Computing and Combina-
torics Conference (COCOON 2018), Qingdao, Jul. 2-4, LNCE vol. 10976, pp.
1-13, 2018.
[22] S.-S. Kao, J.-M. Chang, K.-J. Pai, R.-Y. Wu, Open source for \Constructing
independent spanning trees on bubble-sort networks", (8 Jan. 2018, date online
accessed) https://sites.google.com/ntub.edu.tw/ist-bs/
[23] S. Lakshmivarahan, J. Jwo, S.K. Dhall, Symmetry in interconnection networks
based on Cayley graphs of permutation groups: A survey, Parallel Comput., 19
(1993) 361-407.
[24] K. Qiu, S.G. Akl, H. Meijer, On some properties and algorithms for the star
and pancake interconnection networks, J. Parallel Distrib. Comput., 22 (1994)
16-25.
[25] T.-L. Kung, C.-N. Hung, Estimating the subsystem reliability of bubblesort
networks, Theoret. Comput. Sci., 670 (2017) 45-55.
[26] A.A. Rescigno, Vertex-disjoint spanning trees of the star network with applications
to fault-tolerance and security, Inform. Sci., 137 (2001) 259-276.
[27] S. Sur, P.K. Srimani, Topological properties of star graph, Comput. Math.
Appl., 25 (1993) 87-98.
[28] Y. Suzuki, K. Kaneko, An algorithm for disjoint paths in bubble-sort graphs,
Syst. Comput. Japan 37 (2006) 27-32.
[29] Y. Suzuki, K. Kaneko, The container problem in bubble-sort graphs, IEICE
Trans Inform. Syst., E91-D (2008) 1003-1009.
[30] M. Wang, Y. Guo, S. Wang, The 1-good-neighbour diagnosability of Cayley
graphs generated by transposition trees under the PMC model and MM* model,
Int. J. Comput. Math., 94 (2017) 620-631.
[31] M. Wang, Y. Lin, S. Wang, The 2-good-neighbor diagnosability of Cayley
graphs generated by transposition trees under the PMC model and MM* model,
Theoret. Comput. Sci., 628 (2016) 92-100.
[32] S. Wang, Y. Yang, Fault tolerance in bubble-sort graph networks, Theoret.
Comput. Sci., 421 (2012) 62-69.
[33] Y. Yang, S.Wang, J. Li, Subnetwork preclusion for bubble-sort graph networks,
Inform. Process. Lett., 115 (2015) 817-821.
[34] J.-S. Yang, H.-C. Chan, J.-M. Chang, Broadcasting secure messages via optimal
independent spanning trees in folded hypercubes, Discrete Appl. Math., 159
(2011) 1254-1263.
[35] J.-S. Yang, J.-M. Chang, S.-M. Tang, Y.-L. Wang, Reducing the height of independent
spanning trees in chordal rings, IEEE Trans. Parallel Distrib. Syst.,
18 (2007) 644-657.
[36] J.-S. Yang, S.-S. Luo, J.-M. Chang, Pruning longer branches of independent
spanning trees on folded hyper-stars, Comput. J., 58 (2015) 2979-2981.
[37] J.-S. Yang, M.-R. Wu, J.-M. Chang, Y.-H. Chang, A fully parallelized scheme
of constructing independent spanning trees on Mobius cubes, J. Supercomput.,
71 (2015) 952-965.
[38] A. Zehavi, A. Itai, Three tree-paths, J. Graph Theory, 13 (1989) 175-188.
[39] S. Zhou, J. Wang, X. Xu, J.-M. Xu, Conditional fault diagnosis of bubble sort
graphs under the PMC model, Intel. Comput. Evol. Comput. AISC, 180 (2013)
53-59.