Constructing Node-Independent Spanning Trees in Augmented Cubes

• Autorzy: Cheng Baolei , Fan Jianxi , Lyu Qiang , Lin Cheng-Kuan , Li Xiaoyan , Chen Guo

Identyfikatory

DOI

10.3233/FI-2020-1965

• Języki publikacji: EN

Abstrakty

EN

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQ_n is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n≠3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQ_n. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQ_n is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in AQ_n ( 00...0 _{n – k} ) ( n ≥ k ≥ 4 ) by proposing an ingenious way of construction and propose a corresponding O (N logN ) time algorithm, where N = 2^k is the number of nodes in AQ_n ( 00...0_{n – k ) .}

Słowa kluczowe

EN

augmented cubes; node-independent spanning trees; constructive algorithm; secure message distribution

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 176, nr 2
• Strony: 103--128
• Opis fizyczny: Bibliogr. 48 poz., rys.

Twórcy

autor

Cheng Baolei

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

autor

Fan Jianxi

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

autor

Lyu Qiang

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

autor

Lin Cheng-Kuan

• College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

autor

Li Xiaoyan

• College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

autor

Chen Guo

• School of Computer Science and Technology, Soochow University, Suzhou 215006, China

Bibliografia

• [1] Bao F, Funyu Y, Hamada Y, and Igarashi Y. Reliable broadcasting and secure distributing in channel networks, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81-A, pp. 796-806, 1998. URL http://scholarbank.nus.edu.sg/handle/10635/134137.
• [2] F. Bao, Y. Igarashi, and Öhring SR. Reliable broadcasting in product networks, Discrete Appl. Math., 1998. 83(1-3):3-20. doi:10.1016/s0166-218x(97)00100-5.
• [3] Chen YS, Chiang CY, and Chen CY. Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy, J. Syst. Architect., 2004. 50(9):575-589. doi:10.1016/j.sysarc.2004.01.001.
• [4] Tseng Y-C, Wang S-Y, and Ho C-W. Efficient broadcasting in wormhole-routed multicomputers: A network-partitioning approach, IEEE Trans. Parallel and Distributed Systems, 1999. 10(1):44-61. doi:10.1109/71.744837.
• [5] Elhourani T, Gopalan A, Ramasubramanian S. IP fast rerouting for multi-link failures, IEEE/ACM T. Network., 2016. 24(5):3014-3025. doi:10.1109/tnet.2016.2516442.
• [6] Gopalan A, Ramasubramanian S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees, IEEE/ACM T. Network., 2016. 24(3):1336-1349. doi:10.1109/tnet.2015.2440179.
• [7] Hsieh S-Y, and Wu C-Y. Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults, J. Comb. Optim., 2010. 19(1):16-30. doi:10.1007/s10878-008-9157-x.
• [8] Itai A, and Rodeh M. The multi-tree approach to reliability in distributed networks, Inform. Comput., 1988. 79(1):43-59. doi:10.1016/0890-5401(88)90016-8.
• [9] Zehavi A, and Itai A. Three tree-paths, J. Graph Theory, 1989. 13(2):175-188. doi:org/10.1002/jgt.3190130205.
• [10] Cheriyan J, and Maheshwari SN. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, J. Algorithms, 1988. 9(4): 507-537. doi:10.1016/0196-6774(88)90015-6.
• [11] Curran S, Lee O, and Yu X. Finding four independent trees, SIAM J. Comput., 2006. 35(5):1023-1058. doi:10.1137/s0097539703436734.
• [12] Gopalan A, and Ramasubramanian S. On constructing three edge independent spanning trees, Submitted to SIAM J. Comput., 2011. http://pdfs.semanticscholar.org/b458/a3f665cd41f1ec42fb3cebb5176c369a87ec.pdf.
• [13] Hoyer A, and Thomas R. Four edge-independent spanning trees, SIAM J. Discrete Math., 2018. 32(1):233-248. doi:org/10.1137/17m1134056.
• [14] Huck A. Independent trees in graphs, Graphs and Combinatorics, 1994. 10(1):29-45. doi:10.1007/bf01202468.
• [15] Huck A. Independent trees in planar graphs, Graphs and Combinatorics, 1999. 15(1):29-77. doi:10.1007/pl00021190.
• [16] Miura K, Takahashi D, Nakano S, and Nishizeki T. A linear-time algorithm to find four independent spanning trees in four-connected planar graphs, Int. J. Found. Comput. S., 1999. 10(2):195-210. doi:10.1142/s0129054199000149.
• [17] Nagai S, and Nakano A. A linear-time algorithm to find independent spanning trees in maximal planar graphs, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, 2001. E84-A(5):1102-1109. URL https://search.ieice.org/bin/summary.php?id=e84-a_5 _1102.
• [18] Obokata K, Iwasaki Y, Bao F, and Igarashi Y. Independent spanning trees of product graphs and their construction, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, 1996. E79-A(11):1894-1903. URL https://search.ieice.org/bin/summary.php?id=e79-a_11_1894&category=A&year=1996.
• [19] Iwasaki Y, Kajiwara Y, Obokata K, and Igarashi Y. Independent spanning trees of chordal rings, Inform. Process. Lett., 1999. 69(3):155-160. doi:10.1016/s0020-0190(98)00205-1.
• [20] Yang J-S, Chang J-M, Tang S-M, and Wang Y-L. Reducing the height of independent spanning trees in chordal rings, IEEE Trans. Parallel and Distributed Systems, 2007. 18(5):644-657. doi:10.1109/tpds.2007.351709.
• [21] Ge Z-Y, and Hakimi SL. Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs, SIAM J. Comput., 1997. 26(1):79-92. doi:10.1137/s0097539793244198.
• [22] Kim J-S, Lee H-O, Cheng E, and László L. Independent spanning trees on even networks, Inform. Sciences, 2011. 181(13):2892-2905. doi:10.1016/j.ins.2011.02.012.
• [23] Kim J-S, Lee H-O, Cheng E, and László L. Optimal independent spanning trees on odd graphs, J. Supercomputing, 2011. 56(2):212-225. doi:10.1007/s11227-009-0363-9.
• [24] Cheng B, Fan J, Jia X, and Zhang S. Independent spanning trees in crossed cubes, Inform. Sciences, 2013. 233(1):276-289. doi:10.1016/j.ins.2013.01.010.
• [25] Cheng B, Fan J, Jia X, and Wang J. Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes, J. Parallel Distr. Comput., 2013. 73(5):641-652. doi:10.1016/j.jpdc.2013.01.009.
• [26] Cheng B, Fan J, Lyu Q, Zhou J, and Liu Z. Constructing independent spanning trees with height n on the n-dimensional crossed cube. Futur. Gener. Comput. Syst., 2018. 87:404-415. doi:10.1016/j.future.2018.02.010.
• [27] Cheng B, Fan J, Jia X, Zhang S, Chen B. Constructive algorithm of independent spanning trees on Möbius cubes, Comput. J., 2013. 56(11):1347-1362. doi:10.1093/comjnl/bxs123.
• [28] Cheng B, Fan J, Jia X, and Jia J. Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes, J. Supercomputing, 2013. 65(3):1279-1301. doi:10.1007/s11227-013-0883-1.
• [29] S.-Y. Hsieh and C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theor. Comput. Sci., vol. 410, no. 8-10, pp. 926-932, 2009. https://doi.org/10.1016/j.tcs.2008.12.025.
• [30] Liu Y-J, Chou WY, Lan JK, and Chen C. Constructing independent spanning trees for locally twisted cubes, Theor. Comput. Sci., 2011. 412(22):2237-2252. doi:10.1016/j.tcs.2010.12.061.
• [31] Wang Y, Fan J, Zhou G, and Jia X. Independent spanning trees on twisted cubes, J. Parallel Distr. Comput., 2012. 72(1):58-69. doi:10.1016/j.jpdc.2011.09.002.
• [32] Yang M-C. Constructing edge-disjoint spanning trees in twisted cubes, Inform. Sciences, 2010. 180(20):4075-4083. doi:10.1016/j.ins.2010.05.041.
• [33] Yang J-S, Chang J-M, and Chan H-C. Independent spanning trees on folded hypercubes, in: Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), Kaohsiung, Taiwan, 2009 pp. 73-83. doi:10.1109/i-span.2009.55.
• [34] Cheng B, Fan J, Lin C-K, Jia X, Li X. Constructing node-independent spanning trees on the line graph of the hypercube by an independent forest scheme, J. Parallel Distrib. Comput., 2019. 134:104-115. doi:10.1016/j.jpdc.2019.08.006.
• [35] Yang J-S, and Chang J-M. Independent spanning trees on folded hyper-stars, Networks, 2010. 56(4):272-281. doi:10.1002/net.20389.
• [36] Cheng B, Fan J, Jia X. Dimensional-permutation-based independent spanning trees in bijective connection networks, IEEE Trans. Parallel and Distributed Systems, 2015. 26(1):45-53. doi:10.1109/tpds.2014.2307871.
• [37] Tang S-M, Yang J-S, Wang Y-L, and Chang JM. Independent spanning trees on multidimensional torus networks, IEEE Trans. Comput., 2010. 59(1):93-102. doi:10.1109/tc.2009.98.
• [38] Yang J-S, Chang J-M, Tang S-M, and Wang Y-L. On the independent spanning trees of recursive circulant graphs G(cdm, d) with d > 2, Theor. Comput. Sci., 2009. 410(21-23):2001-2010. doi:10.1016/j.tcs.2008.12.042.
• [39] Chan H-C, Chang J-M, Wang Y-L, and Horng S-J. Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Appl. Math. Comput., 2009. 207(2):333-339. doi:10.1016/j.amc.2008.10.061.
• [40] Cheng D, Hao R-X, and Feng Y-Q. Conditional edge-fault pancyclicity of augmented cubes, Theor. Comput. Sci., vol. 2013. 510:94-101. doi:10.1016/j.tcs.2013.09.010.
• [41] Choudum SA, and Sunitha V. Augmented cubes, Networks, 2002. 40(2):71-84. doi:10.1002/net.10033.
• [42] Fu J-S. Edge-fault-tolerant vertex-pancyclicity of augmented cubes, Inf. Process. Lett., 2010. 110(11):439-443. doi:10.1016/j.ipl.2010.04.009.
• [43] Hsieh S-Y, and Cian Y-R. Conditional edge-fault Hamiltonicity of augmented cubes, Inform. Sciences, 2010. 180(13):2596-2617. doi:10.1016/j.ins.2010.03.005.
• [44] Ma M, Liu G, Xu J-M. The super connectivity of augmented cubes, Inf. Process. Lett., 2008. 106(2):59-63. doi:10.1016/j.ipl.2007.10.005.
• [45] Mane SA, Kandekar SA, Waphare BN. Constructing spanning trees in augmented cubes, J. Parallel Distrib. Comput., 2018. 122:188-194. doi10.1016/j.jpdc.2018.08.006.
• [46] Wang Y, Shen H, Fan J. Edge-independent spanning trees in augmented cubes, Theor. Comput. Sci., 2017. 670:23-32. doi:10.1016/j.tcs.2017.01.016.
• [47] Cheng B, Fan J, Lin C-K, Wang Y, and Jia X. An improved algorithm to construct edge-independent spanning trees in augmented cubes, Discrete Appl. Math., 2020. 277:55-70. doi:10.1016/j.dam.2019.09.021.
• [48] Tang S-M, Wang Y-L, and Lee JX. On the height of independent spanning trees of a k-connected k-regular graph, Proceedings of National Computer Symposium. 2001: A159-A164. URL https://www.researchgate.net/publication/248789350_On_the_height_of_independent_spanning_trees_of_a_k_ - _connected_k_ -_regular_graph.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).