×

Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks. (English) Zbl 1430.90490

Summary: 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)\) 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\) and bubble-sort network \(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\) (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\) is not dealt with yet. In this paper, we present an algorithm to construct \(n-1\) ISTs of \(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.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akers SB, Krishnamurty B (1989) A group theoretic model for symmetric interconnection networks. IEEE Trans Comput 38:555-566 · Zbl 0678.94026 · doi:10.1109/12.21148
[2] Araki T, Kikuchi Y (2007) Hamiltonian laceability of bubble-sort graphs with edge faults. Inf Sci 177:2679-2691 · Zbl 1115.68106 · doi:10.1016/j.ins.2007.01.017
[3] Bao F, Funyu Y, Hamada Y, Igarashi Y (1997) Reliable broadcasting and secure distributing in channel networks. In: Proceedings of 3rd international symposium on parallel architectures, algorithms and networks (I-SPAN’97), pp 472-478
[4] Chang Y-H, Yang J-S, Hsieh S-Y, Chang J-M, Wang Y-L (2017a) Construction independent spanning trees on locally twisted cubes in parallel. J Comb Optim 33:956-967 · Zbl 1367.05032 · doi:10.1007/s10878-016-0018-8
[5] Chang J-M, Yang T-J, Yang J-S (2017b) A parallel algorithm for constructing independent spanning trees in twisted cubes. Discrete Appl Math 219:74-82 · Zbl 1354.05025 · doi:10.1016/j.dam.2016.11.017
[6] Chen X, Fan J, Lin C-K, Cheng B, Liu Z (2015) A VoD system model based on BC graphs. In: Proceedings of 4th national conference on electrical, electronics and computer engineering (NCEECE 2015), Xian, China, December 12-13, pp 1499-1505
[7] Cheng B, Fan J, Lyu Q, Zhou J, Liu Z (2018) Constructing independent spanning trees with height \[n\] n on the \[n\] n-dimensional crossed cube. Future Gener Comput Syst 87:404-415 · doi:10.1016/j.future.2018.02.010
[8] Cheriyan J, Maheshwari SN (1988) Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J Algorithms 9:507-537 · Zbl 0672.05056 · doi:10.1016/0196-6774(88)90015-6
[9] Chiang W-K, Chen R-J (1995) The \[(n, k)\](n,k)-star graph: a generalized star graph. Inf Process Lett 56:259-264 · Zbl 1027.68645 · doi:10.1016/0020-0190(95)00162-1
[10] Curran S, Lee O, Yu X (2006) Finding four independent trees. SIAM J Comput 35:1023-1058 · Zbl 1101.05064 · doi:10.1137/S0097539703436734
[11] da Silva ESA, Pedrini H (2016a) Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees. Comput Biol Med 70:51-57 · doi:10.1016/j.compbiomed.2016.01.004
[12] da Silva ESA, Pedrini H (2016b) Connected-component labeling based on hypercubes for memory constrained scenarios. Expert Syst Appl 61:272-281 · doi:10.1016/j.eswa.2016.06.002
[13] Day K, Tripathi A (1992) Arrangement graphs: a class of generalized star graphs. Inf Process Lett 42:235-241 · Zbl 0772.68005 · doi:10.1016/0020-0190(92)90030-Y
[14] Guo C, Lu G, Xiong Y, Cao J, Zhu Y, Chen C, Zhang Y (2011) Datacast: a scalable and efficient group data delivery service for data centers. Report MSR-TR-2011-76 from Microsoft Research Asia
[15] Hao R-X, Tian Z-X, Xu J-M (2012) Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs. Theor Comput Sci 627:36-53 · Zbl 1338.68030 · doi:10.1016/j.tcs.2016.02.024
[16] IEEE (2006) 802.1s—multiple spanning trees. http://www.ieee802.org/1/pages/802.1s.html. Accessed 8 June 2019
[17] Itai A, Rodeh M (1988) The multi-tree approach to reliability in distributed networks. Inf Comput 79:43-59 · Zbl 0655.68029 · doi:10.1016/0890-5401(88)90016-8
[18] Johnsson SL, Ho C-T (1989) Optimum broadcasting and personalized communication in hypercubes. IEEE Trans Comput 38:1249-1268 · Zbl 1395.68034 · doi:10.1109/12.29465
[19] Jwo J, Lakshmivarahan S, Dhall SK (1993) A new class of interconnection networks based on the alternating group. Networks 23:315-326 · Zbl 0774.90031 · doi:10.1002/net.3230230414
[20] Kao S-S, Chang J-M, Pai K-J, Yang J-S, Tang S-M, Wu R-Y (2017) A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks. In: Proceedings of 11th international conference on combinatorial optimization and applications (COCOA 2017), Shanghai, December 16-18, vol 10627. LNCS, pp 472-478 · Zbl 1470.68061
[21] Kao S-S, Chang J-M, Pai K-J, Wu R-Y (2018) Open source for “Constructing independent spanning trees on bubble-sort networks”. https://sites.google.com/ntub.edu.tw/ist-bs/. Accessed 8 Aug 2018
[22] Kikuchi Y, Araki T (2006) Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Inf Process Lett 100:52-59 · Zbl 1185.05090 · doi:10.1016/j.ipl.2006.05.012
[23] Kung T-L, Hung C-N (2017) Estimating the subsystem reliability of bubblesort networks. Theor Comput Sci 670:45-55 · Zbl 1359.68028 · doi:10.1016/j.tcs.2017.01.021
[24] Lakshmivarahan S, Jwo J, Dhall SK (1993) Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey. Parallel Comput 19:361-407 · Zbl 0777.05064 · doi:10.1016/0167-8191(93)90054-O
[25] Rescigno AA (2001) Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security. Inf Sci 137:259-276 · Zbl 0996.68024 · doi:10.1016/S0020-0255(01)00121-9
[26] Sharma S, Gopalan K, Nanda S, Chiueh T (2004) Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks. In: Proceedings of 23rd annual joint conference of the IEEE computer and communications societies (INFOCOM’04), Hong Kong, China, March 7-11, pp 1408-1417
[27] Suzuki Y, Kaneko K (2006) An algorithm for disjoint paths in bubble-sort graphs. Syst Comput Jpn 37:27-32 · doi:10.1002/scj.20518
[28] Suzuki Y, Kaneko K (2008) The container problem in bubble-sort graphs. IEICE Trans Inf Syst E91-D:1003-1009 · doi:10.1093/ietisy/e91-d.4.1003
[29] Wang S, Yang Y (2012) Fault tolerance in bubble-sort graph networks. Theor Comput Sci 421:62-69 · Zbl 1232.68024 · doi:10.1016/j.tcs.2011.11.016
[30] Wang M, Guo Y, Wang S (2017) The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Int J Comput Math 94:620-631 · Zbl 1362.05062 · doi:10.1080/00207160.2015.1119817
[31] Wang M, Lin Y, Wang S (2016) The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Theor Comput Sci 628:92-100 · Zbl 1338.68036 · doi:10.1016/j.tcs.2016.03.019
[32] Yang J-S, Chan H-C, Chang J-M (2011) Broadcasting secure messages via optimal independent spanning trees in folded hypercubes. Discrete Appl Math 159:1254-1263 · Zbl 1225.68138 · doi:10.1016/j.dam.2011.04.014
[33] Yang Y, Wang S, Li J (2015) Subnetwork preclusion for bubble-sort graph networks. Inf Process Lett 115:817-821 · Zbl 1331.68025 · doi:10.1016/j.ipl.2015.06.011
[34] Zehavi A, Itai A (1989) Three tree-paths. J Graph Theory 13:175-188 · Zbl 0698.05049 · doi:10.1002/jgt.3190130205
[35] Zhou S, Wang J, Xu X, Xu J-M (2013) Conditional fault diagnosis of bubble sort graphs under the PMC model. Intell Comput Evol Comput AISC 180:53-59
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.