Recursive and parallel constructions of independent spanning trees in alternating group networks

References

• S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (1989), pp. 555–566. doi: 10.1109/12.21148
   Web of Science ®Google Scholar
• F. Bao, Y. Funyu, Y. Hamada, and 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.
   Google Scholar
• Y.H. Chang, J.S. Yang, J.M. Chang, and Y.L. Wang, A fast parallel algorithm for constructing independent spanning trees on parity cubes, Appl. Math. Comput. 268 (2015), pp. 489–495.
   Web of Science ®Google Scholar
• J.M. Chang, T.J. Yang, and J.S. Yang, A parallel algorithm for constructing independent spanning trees in twisted cubes, Discr. Appl. Math. 219 (2017), pp. 74–82. doi: 10.1016/j.dam.2016.11.017
   Web of Science ®Google Scholar
• Y.H. Chang, J.S. Yang, S.Y. Hsieh, J.M. Chang, and Y.L. Wang, Construction independent spanning trees on locally twisted cubes in parallel, J. Combinat. Optim. 33 (2017), pp. 956–967. doi: 10.1007/s10878-016-0018-8
   Web of Science ®Google Scholar
• B. Chen, W. Xiao, and B. Parhami, Internode distance and optimal routing in a class of alternating group networks, IEEE Trans. Comput. 55(12) (2006), pp. 1645–1648. doi: 10.1109/TC.2006.199
   Web of Science ®Google Scholar
• B.L. Cheng, J.X. Fan, X.H. Jia, S.K. Zhang, and B.R. Chen, Constructive algorithm of independent spanning trees on Möbius cubes, The Comput. J. 56(11) (2013), pp. 1347–1362. doi: 10.1093/comjnl/bxs123
   Web of Science ®Google Scholar
• B.L Cheng, J.X. Fan, X.H. Jia, and S.K. Zhang, Independent spanning trees in crossed cubes, Inform. Sci. 233 (2013), pp. 276–289. doi: 10.1016/j.ins.2013.01.010
   Web of Science ®Google Scholar
• J. Cheriyan and S.N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, J. Alg. 9(4) (1988), pp. 507–537. doi: 10.1016/0196-6774(88)90015-6
   Google Scholar
• S. Curran, O. Lee, and X.X. Yu, Finding four independent trees, SIAM J. Comput. 35(5) (2006), pp. 1023–1058. doi: 10.1137/S0097539703436734
   Web of Science ®Google Scholar
• Y.O. Hamidoune, A.S. Llado, and O. Serra, The connectivity of hierarchical cayley digraphs, Discr. Appl. Math. 37–38 (1992), pp. 275–280. doi: 10.1016/0166-218X(92)90138-Z
   Web of Science ®Google Scholar
• S.Y. Hsieh and C.J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theor. Comput. Sci. 410 (2009), pp. 926–932. doi: 10.1016/j.tcs.2008.12.025
   Web of Science ®Google Scholar
• A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput. 79(1) (1988), pp. 43–59. doi: 10.1016/0890-5401(88)90016-8
   Web of Science ®Google Scholar
• J.S. Jwo, S. Lakshmivarahan, and S.K. Dhall, A new class of interconnection networks based on the alternating groups, Networks 23 (1993), pp. 315–326. doi: 10.1002/net.3230230414
   Web of Science ®Google Scholar
• S.S. Kao, J.M. Chang, K.J. Pai, and R.Y. Wu, Constructing independent spanning trees on bubble-sort networks, in International Computing and Combinatorics Conference, COCOON2018, Vol. 10976, 2018, Springer, Cham, pp. 1–13.
   Google Scholar
• S.S. Kao, K.J. Pai, S.Y. Hsieh, R.Y. Wu, and J.M. Chang, Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks, J. Combinat. Optim. 38(3) (2019), pp. 972–986. doi: 10.1007/s10878-019-00430-0
   Web of Science ®Google Scholar
• S. Lakshmivarahan, J.S. Jwo, and S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutations: A survey, Parallel Comput. 19 (1993), pp. 361–407. doi: 10.1016/0167-8191(93)90054-O
   Web of Science ®Google Scholar
• Y.J. Liu, J.K. Lan, W.Y. Chou, and C. Chen, Constructing independent spanning trees for locally twisted cubes, Theor. Comput. Sci. 412 (2011), pp. 2237–2252. doi: 10.1016/j.tcs.2010.12.061
   Web of Science ®Google Scholar
• A.A. Rescigno, Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security, Inform. Sci. 137 (2001), pp. 259–276. doi: 10.1016/S0020-0255(01)00121-9
   Web of Science ®Google Scholar
• E. Silva and H. Pedrini, Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees, Comput. Biol. Med. 70 (2016), pp. 51–57. doi: 10.1016/j.compbiomed.2016.01.004
   PubMed Web of Science ®Google Scholar
• Y. Wang, J.X. Fan, X.H. Jia, and H. Huang, An algorithm to construct independent spanning trees on parity cubes, Theor. Comput. Sci. 465 (2012), pp. 61–72. doi: 10.1016/j.tcs.2012.08.020
   Web of Science ®Google Scholar
• Y. Wang, J.X. Fan, G.D. Zhou, and X.H. Jia, Independent spanning trees on twisted cubes, J. Parallel Distribut. Comput. 72 (2012), pp. 58–69. doi: 10.1016/j.jpdc.2011.09.002
   Web of Science ®Google Scholar
• J. Werapun, S. Intakosum, and V. Boonjing, An efficient parallel construction of optimal independent spanning trees on hypercubes, J. Parallel Distribut. Comput. 72(12) (2012), pp. 1713–1724. doi: 10.1016/j.jpdc.2012.07.003
   Web of Science ®Google Scholar
• J.S. Yang, J.M. Chang, S.M. Tang, and Y.L. Wang, Parallel construction of optimal independent spanning trees on hypercubes, Parallel Comput. 33 (2007), pp. 73–79. doi: 10.1016/j.parco.2006.12.001
   Web of Science ®Google Scholar
• J.S. Yang, H.C. Chan, and J.M. Chang, Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Discr. Appl. Math. 159(12) (2011), pp. 1254–1263. doi: 10.1016/j.dam.2011.04.014
   Web of Science ®Google Scholar
• J. Youhu, A new class of cayley networks based on the alternating groups, Appl. Math. JCU 14(A)(2) (1998), pp. 235–239. in Chinese.
   Google Scholar
• S. Zhou, W. Xiao, and B. Parhami, Construction of vertex-disjoint paths in alternating group networks, Supercomputing 54(2) (2010), pp. 206–228. doi: 10.1007/s11227-009-0304-7
   Web of Science ®Google Scholar
• A. Zehavi and A. Itai, Three tree-paths, J. Graph. Theory 13(2) (1989), pp. 175–188. doi: 10.1002/jgt.3190130205
   Web of Science ®Google Scholar