×

A parallel algorithm for constructing independent spanning trees in twisted cubes. (English) Zbl 1354.05025

Summary: A long-standing conjecture mentions that a \(k\)-connected graph \(G\) admits \(k\) independent spanning trees (ISTs for short) rooted at an arbitrary node of \(G\). An \(n\)-dimensional twisted cube, denoted by \(T Q_n\), is a variation of hypercube with connectivity \(n\) and has many features superior to those of hypercube. M.-C. Yang [Inf. Sci. 180, No. 20, 4075–4083 (2010; Zbl 1209.68387)] first proposed an algorithm to construct \(n\) edge-disjoint spanning trees in \(T Q_n\) for any odd integer \(n \geqslant 3\) and showed that half of them are ISTs. At a later stage, Y. Wang et al. [J. Parallel Distrib. Comput. 72, No. 1, 58–69 (2012; Zbl 1231.68093)] inferred that the above conjecture in affirmative for \(T Q_n\) by providing an \(\mathcal{O}(N \log N)\) time algorithm to construct \(n\) ISTs, where \(N = 2^n\) is the number of nodes in \(T Q_n\). However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we revisit the problem of constructing ISTs in twisted cubes and present a non-recursive algorithm. Our approach can be fully parallelized to make the use of all nodes of \(T Q_n\) as processors for computation in such a way that each node can determine its parent in all spanning trees directly by referring its address and tree indices in \(\mathcal{O}(\log N)\) time.

MSC:

05C05 Trees
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C40 Connectivity
68W10 Parallel algorithms in computer science
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abraham, S.; Padmanabhan, K., The twisted cube topology for multiprocessors: a study in network asymmetry, J. Parallel Distrib. Comput., 13, 104-110 (1991)
[3] Chang, C.-P.; Wang, J.-N.; Hsu, L.-H., Topological properties of twisted cubes, Inform. Sci., 113, 147-167 (1999) · Zbl 0952.68008
[4] Chang, J.-M.; Wang, J.-D.; Yang, J.-S.; Pai, K.-J., A comment on independent spanning trees in crossed cubes, Inform. Process. Lett., 114, 734-739 (2014) · Zbl 1358.68020
[5] Chang, Y.-H.; Yang, J.-S.; Chang, J.-M.; Wang, Y.-L., A fast parallel algorithm for constructing independent spanning trees on parity cubes, Appl. Math. Comput., 268, 489-495 (2015) · Zbl 1410.05195
[6] Cheriyan, J.; Maheshwari, S. N., Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, J. Algorithms, 9, 507-537 (1988) · Zbl 0672.05056
[7] Curran, S.; Lee, O.; Yu, X., Finding four independent trees, SIAM J. Comput., 35, 1023-1058 (2006) · Zbl 1101.05064
[8] Fan, J.; Jia, X.; Lin, X., Optimal embeddings of paths with various lengths in twisted cubes, IEEE Trans. Parallel Distrib. Syst., 18, 511-521 (2007)
[9] Fan, J.; Jia, X.; Lin, X., Embedding of cycles in twisted cubes with edge-pancyclic, Algorithmica, 51, 264-282 (2008) · Zbl 1203.68023
[10] Fan, J.; Lin, X.; Pan, Y.; Jia, X., Optimal fault-tolerant embedding of paths in twisted cubes, IEEE Trans. Parallel Distrib. Syst., 67, 205-214 (2007) · Zbl 1158.68336
[11] Hilbers, P. A.J.; Koopman, M. R.J.; van de Snepscheut, J. L.A., The twisted cube, (Parallel Architectures and Languages Europe, Vol. 1: Parallel Architectures. Parallel Architectures and Languages Europe, Vol. 1: Parallel Architectures, Lecture Notes in Computer Science, vol. 258 (1987)), 152-159
[12] Hsieh, S.-Y.; Tu, C.-J., Constructing edge-disjoint spanning trees in locally twisted cubes, Theoret. Comput. Sci., 410, 926-932 (2009) · Zbl 1162.68046
[13] Itai, A.; Rodeh, M., The multi-tree approach to reliability in distributed networks, Inform. Comput., 79, 43-59 (1988) · Zbl 0655.68029
[14] Lai, P.-L., Geodesic pancyclicity of twisted cubes, Inform. Sci., 181, 5321-5332 (2011) · Zbl 1248.68095
[15] Lai, P.-L., Paths and cycles identifying vertices in twisted cubes, Appl. Math. Comput., 259, 620-627 (2015) · Zbl 1392.68076
[16] Lai, C.-J.; Tsai, C.-H., Embedding a family of meshes into twisted cubes, Inform. Process. Lett., 108, 326-330 (2008) · Zbl 1191.68042
[17] Lai, P.-L.; Tsai, C.-H., Embedding of tori and grids into twisted cubes, Theoret. Comput. Sci., 411, 3763-3773 (2010) · Zbl 1208.68047
[18] Rescigno, A. A., Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security, Inform. Sci., 137, 259-276 (2001) · Zbl 0996.68024
[19] Wang, Y.; Fan, J.; Zhou, G.; Jia, X., Independent spanning trees on twisted cubes, J. Parallel Distrib. Comput., 72, 58-69 (2012) · Zbl 1231.68093
[20] Yang, M.-C., Edge-fault-tolerant node-pancyclicity of twisted cubes, Inform. Process. Lett., 109, 1206-1210 (2009) · Zbl 1206.68044
[21] Yang, M.-C., Constructing edge-disjoint spanning trees in twisted cubes, Inform. Sci., 180, 4075-4083 (2010) · Zbl 1209.68387
[22] Yang, J.-S.; Chan, H.-C.; Chang, J.-M., Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Discrete Appl. Math., 159, 1254-1263 (2011) · Zbl 1225.68138
[23] Yang, J.-S.; Chang, J.-M., Optimal independent spanning trees on Cartesian product of hybrid graphs, Comput. J., 57, 93-99 (2014)
[24] Yang, J.-S.; Chang, J.-M.; Pai, K.-J.; Chan, H.-C., Parallel construction of independent spanning trees on enhanced hypercubes, IEEE Trans. Parallel Distrib. Syst., 26, 3090-3098 (2015)
[25] Yang, M.-C.; Li, T.-K.; Tan, J.-M.; Hsu, L.-H., On embedding cycles into faulty twisted cubes, Inform. Sci., 176, 676-690 (2007) · Zbl 1103.68028
[26] Yang, J.-S.; Luo, S.-S.; Chang, J.-M., Pruning longer branches of independent spanning trees on folded hyper-stars, Comput. J., 58, 2972-2981 (2015)
[27] Yang, J.-S.; Tang, S.-M.; Chang, J.-M.; Wang, Y.-L., Parallel construction of optimal independent spanning trees on hypercubes, Parallel Comput., 33, 73-79 (2007)
[28] Yang, J.-S.; Wu, M.-R.; Chang, J.-M.; Chang, Y.-H., A fully parallelized scheme of constructing independent spanning trees on Möbius cubes, J. Supercomput., 71, 894-908 (2015)
[29] Zehavi, A.; Itai, A., Three tree-paths, J. Graph Theory, 13, 175-188 (1989) · Zbl 0698.05049
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.