{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T02:00:06Z","timestamp":1792461606345,"version":"4.5.0"},"reference-count":131,"publisher":"Association for Computing Machinery (ACM)","issue":"14s","license":[{"start":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T00:00:00Z","timestamp":1689552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62272333, 62172291, U1905211"],"award-info":[{"award-number":["62272333, 62172291, U1905211"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Jiangsu Province Department of Education Future Network Scientific Research Fund Project","award":["FNSRFP-2021-YB-39"],"award-info":[{"award-number":["FNSRFP-2021-YB-39"]}]},{"DOI":"10.13039\/501100012246","name":"Priority Academic Program Development of Jiangsu Higher Education Institutions","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Collaborative Innovation Center of Novel Software Technology and Industrialization"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            The problem of constructing independent spanning trees (ISTs) dates back to as early as the late 1980s. Given a network\n            <jats:italic>G<\/jats:italic>\n            of a certain topology, the question is whether we can, as well as how to, construct a set of ISTs in\n            <jats:italic>G<\/jats:italic>\n            . ISTs have proven to be of great importance in many network tasks. The past decade has seen a particularly remarkable increase in the literature on ISTs, manifesting a significant growth of interest. ISTs can be classified into edge-independent spanning trees (edge-ISTs), node-independent spanning trees (node-ISTs), and completely independent spanning trees (CISTs). For a network\n            <jats:italic>G<\/jats:italic>\n            , node-ISTs (edge-ISTs) rooted at\n            <jats:italic>u<\/jats:italic>\n            are a set of spanning trees rooted at\n            <jats:italic>u<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            such that there are no common internal nodes (edges) between\n            <jats:italic>u<\/jats:italic>\n            and any other node among the paths in these spanning trees. If every node in a set of node-ISTs can act as a root node, the set of trees is called\n            <jats:italic>CISTs<\/jats:italic>\n            . This survey aims at bringing together important works on ISTs that have been reported in the literature. It provides a historical perspective of how the field has evolved, and can serve as an integrated useful resource of references for future research on ISTs.\n          <\/jats:p>","DOI":"10.1145\/3591110","type":"journal-article","created":{"date-parts":[[2023,4,4]],"date-time":"2023-04-04T12:22:39Z","timestamp":1680610959000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Independent Spanning Trees in Networks: A Survey"],"prefix":"10.1145","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9479-8372","authenticated-orcid":false,"given":"Baolei","family":"Cheng","sequence":"first","affiliation":[{"name":"Soochow University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4247-3909","authenticated-orcid":false,"given":"Dajin","family":"Wang","sequence":"additional","affiliation":[{"name":"Montclair State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7055-5891","authenticated-orcid":false,"given":"Jianxi","family":"Fan","sequence":"additional","affiliation":[{"name":"Soochow University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,17]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1768-x"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21780"},{"key":"e_1_3_1_4_2","unstructured":"F. Bao Y. Funyu Y. Hamada and Y. Igarashi. 1998. Reliable broadcasting and secure distributing in channel networks. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E81-A 5 (1998) 796\u2013806.  F. Bao Y. Funyu Y. Hamada and Y. Igarashi. 1998. Reliable broadcasting and secure distributing in channel networks. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E81-A 5 (1998) 796\u2013806."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00033-2"},{"key":"e_1_3_1_6_2","volume-title":"Proceedings of the 21st International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201921)","author":"Bian Q.","unstructured":"Q. Bian , B. Cheng , J. Fan , and Z. Pan . 2021. Completely independent spanning trees in the line graph of torus networks . In Proceedings of the 21st International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201921) 540\u2013553. Q. Bian, B. Cheng, J. Fan, and Z. Pan. 2021. Completely independent spanning trees in the line graph of torus networks. In Proceedings of the 21st International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201921) 540\u2013553."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1587\/transfun.E98.A.2191"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.06.081"},{"key":"e_1_3_1_9_2","volume-title":"Proceedings of the 2017 2nd International Conference on Computer Science and Technology (CST\u201917)","author":"Chang J.-M.","year":"2017","unstructured":"J.-M. Chang . 2017 . Computing the wide diameter of regular hyper-star networks using independent spanning trees . In Proceedings of the 2017 2nd International Conference on Computer Science and Technology (CST\u201917) . 335\u2013340. J.-M. Chang. 2017. Computing the wide diameter of regular hyper-star networks using independent spanning trees. In Proceedings of the 2017 2nd International Conference on Computer Science and Technology (CST\u201917). 335\u2013340."},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"J.-M. Chang H.-Y. Chang H.-L. Wang K.-J. Pai and J.-S. Yang. 2017. Completely independent spanning trees on 4-regular chordal rings. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E100A 9 (2017) 1932\u20131935.  J.-M. Chang H.-Y. Chang H.-L. Wang K.-J. Pai and J.-S. Yang. 2017. Completely independent spanning trees on 4-regular chordal rings. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E100A 9 (2017) 1932\u20131935.","DOI":"10.1587\/transfun.E100.A.1932"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.06.015"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.11.017"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0018-8"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3029654"},{"key":"e_1_3_1_15_2","volume-title":"US Patent ZL201910811364","author":"Chen G.","year":"2021","unstructured":"G. Chen , B. Cheng , J. Fan , D. Wang , and Y. Wang . 2019. A secure distribution method for data . US Patent ZL201910811364 .0, July 9, 2021 . G. Chen, B. Cheng, J. Fan, D. Wang, and Y. Wang. 2019. A secure distribution method for data. US Patent ZL201910811364.0, July 9, 2021."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2013.07.016"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.11.018"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-022-00863-0"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.11.019"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2307871"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2013.01.010"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-013-0883-1"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.01.009"},{"key":"e_1_3_1_24_2","volume-title":"Proceedings of the 18th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201918)","author":"Cheng B.","unstructured":"B. Cheng , J. Fan , X. Li , G. Wang , J. Zhou , and Y. Han . 2018. Towards the independent spanning trees in the line graphs of interconnection networks . In Proceedings of the 18th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201918) . 342\u2013354. B. Cheng, J. Fan, X. Li, G. Wang, J. Zhou, and Y. Han. 2018. Towards the independent spanning trees in the line graphs of interconnection networks. In Proceedings of the 18th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201918). 342\u2013354."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.08.006"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.09.021"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"103","DOI":"10.3233\/FI-2020-1965","article-title":"Constructing node-independent spanning trees in augmented cubes","volume":"176","author":"Cheng B.","year":"2020","unstructured":"B. Cheng , J. Fan , Q. Lyu , C.-K. Lin , X. Li , and G. Chen . 2020 . Constructing node-independent spanning trees in augmented cubes . Fundamenta Informaticae 176 (2020), 103 \u2013 128 . B. Cheng, J. Fan, Q. Lyu, C.-K. Lin, X. Li, and G. Chen. 2020. Constructing node-independent spanning trees in augmented cubes. Fundamenta Informaticae 176 (2020), 103\u2013128.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2018.02.010"},{"key":"e_1_3_1_29_2","volume-title":"US Patent ZL201811146867","author":"Cheng B.","year":"2021","unstructured":"B. Cheng , J. Fan , J. Yang , G. Chen , and Z. Liu . 2018. A data center network based on augmented cube and its server fault-tolerant broadcasting method . US Patent ZL201811146867 .2, December 31, 2021 . B. Cheng, J. Fan, J. Yang, G. Chen, and Z. Liu. 2018. A data center network based on augmented cube and its server fault-tolerant broadcasting method. US Patent ZL201811146867.2, December 31, 2021."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxs123"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2962549"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90015-6"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434592"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436734"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434580"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.09.007"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.11.018"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.06.002"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118740.3118865"},{"key":"e_1_3_1_40_2","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.ipl.2013.04.008","article-title":"A counterexample for the proof of implication conjecture on independent spanning trees","volume":"113","author":"Gopalan A.","year":"2013","unstructured":"A. Gopalan and S. Ramasubramanian . 2013 . A counterexample for the proof of implication conjecture on independent spanning trees . Information Processing Letters 113 , 14 \u2013 16 (2013), 522\u2013526. A. Gopalan and S. Ramasubramanian. 2013. A counterexample for the proof of implication conjecture on independent spanning trees. Information Processing Letters 113, 14\u201316 (2013), 522\u2013526.","journal-title":"Information Processing Letters"},{"key":"e_1_3_1_41_2","unstructured":"A. Gopalan and S. Ramasubramanian. 2011. On constructing three edge independent spanning trees. Unpublished manuscript. Available at https:\/\/www.semanticscholar.org\/paper\/ON-CONSTRUCTING-THREE-EDGE-INDEPENDENT-SPANNING-Gopalan\/b458a3f665cd41f1ec42fb3cebb5176c369a87ec?p2df.  A. Gopalan and S. Ramasubramanian. 2011. On constructing three edge independent spanning trees. Unpublished manuscript. Available at https:\/\/www.semanticscholar.org\/paper\/ON-CONSTRUCTING-THREE-EDGE-INDEPENDENT-SPANNING-Gopalan\/b458a3f665cd41f1ec42fb3cebb5176c369a87ec?p2df."},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2440179"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/3287775.3287808"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2017.12.018"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.05.059"},{"key":"e_1_3_1_46_2","volume-title":"Combinatorial Optimization and Applications. Lecture Notes in Computer Science","volume":"10043","author":"Gregor P.","unstructured":"P. Gregor , R. \u0160krekovski , and V. Vuka\u0161inovic . 2016. Time-optimal broadcasting of multiple messages in 1-in port model . In Combinatorial Optimization and Applications. Lecture Notes in Computer Science , Vol. 10043 . Springer, 144\u2013158. P. Gregor, R. \u0160krekovski, and V. Vuka\u0161inovic. 2016. Time-optimal broadcasting of multiple messages in 1-in port model. In Combinatorial Optimization and Applications. Lecture Notes in Computer Science, Vol. 10043. Springer, 144\u2013158."},{"key":"e_1_3_1_47_2","volume-title":"Independent spanning trees of 2-chordal rings. IEICETransactions on Fundamentals of Electronics, Communications and Computer Sciences E99A 1","author":"Hamada Y.","year":"2016","unstructured":"Y. Hamada . 2016. Independent spanning trees of 2-chordal rings. IEICETransactions on Fundamentals of Electronics, Communications and Computer Sciences E99A 1 ( 2016 ), 355\u2013362. Y. Hamada. 2016. Independent spanning trees of 2-chordal rings. IEICETransactions on Fundamentals of Electronics, Communications and Computer Sciences E99A 1 (2016), 355\u2013362."},{"key":"e_1_3_1_48_2","series-title":"Lecture Notes in Computer Science","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Hasunuma T.","unstructured":"T. Hasunuma . 2002. Completely independent spanning trees in maximal planar graphs . In Graph-Theoretic Concepts in Computer Science . Lecture Notes in Computer Science , Vol. 2573 . Springer , 235\u2013245. T. Hasunuma. 2002. Completely independent spanning trees in maximal planar graphs. In Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, Vol. 2573. Springer, 235\u2013245."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00377-0"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20460"},{"key":"e_1_3_1_51_2","volume-title":"Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA\u201915)","author":"Hasunuma T.","year":"2015","unstructured":"T. Hasunuma . 2015 . Minimum degree conditions and optimal graphs for completely independent spanning trees . In Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA\u201915) . 260\u2013273. T. Hasunuma. 2015. Minimum degree conditions and optimal graphs for completely independent spanning trees. In Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA\u201915). 260\u2013273."},{"key":"e_1_3_1_52_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0166-218X(00)00269-9","article-title":"Independent spanning trees with small depths in iterated line digraphs","volume":"110","author":"Hasunuma T.","year":"2001","unstructured":"T. Hasunuma and H. Nagamochi . 2001 . Independent spanning trees with small depths in iterated line digraphs . Discrete Applied Mathematics 110 , 2 \u2013 3 (2001), 189\u2013211. T. Hasunuma and H. Nagamochi. 2001. Independent spanning trees with small depths in iterated line digraphs. Discrete Applied Mathematics 110, 2\u20133 (2001), 189\u2013211.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.01.008"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.013"},{"key":"e_1_3_1_55_2","volume-title":"Proceedings of the 1990 International Conference on Parallel Processing. 276\u2013280","author":"Ho C.-T.","year":"1990","unstructured":"C.-T. Ho . 1990 . Full bandwidth communications on folded hypercubes . In Proceedings of the 1990 International Conference on Parallel Processing. 276\u2013280 . C.-T. Ho. 1990. Full bandwidth communications on folded hypercubes. In Proceedings of the 1990 International Conference on Parallel Processing. 276\u2013280."},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.2038"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.05.004"},{"key":"e_1_3_1_58_2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2019.08.013","article-title":"A Hamilton sufficient condition for completely independent spanning tree","volume":"279","author":"Hong X.","year":"2020","unstructured":"X. Hong and H. Zhang . 2020 . A Hamilton sufficient condition for completely independent spanning tree . Discrete Applied Mathematics 279 (2020), 183 \u2013 187 . X. Hong and H. Zhang. 2020. A Hamilton sufficient condition for completely independent spanning tree. Discrete Applied Mathematics 279 (2020), 183\u2013187.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1134056"},{"key":"e_1_3_1_60_2","first-page":"8","article-title":"Constructing edge-disjoint spanning trees in locally twisted cubes","volume":"410","author":"Hsieh S.-Y.","year":"2009","unstructured":"S.-Y. Hsieh and C.-J. Tu . 2009 . Constructing edge-disjoint spanning trees in locally twisted cubes . Theoretical Computer Science 410 , 8 \u2013 10 (2009), 926\u2013932. S.-Y. Hsieh and C.-J. Tu. 2009. Constructing edge-disjoint spanning trees in locally twisted cubes. Theoretical Computer Science 410, 8\u201310 (2009), 926\u2013932.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_1_61_2","doi-asserted-by":"crossref","first-page":"112333","DOI":"10.1109\/ACCESS.2020.2999421","article-title":"Top-down construction of independent spanning trees in alternating group networks","volume":"8","author":"Huang J.-F.","year":"2020","unstructured":"J.-F. Huang , S.-S. Kao , S.-Y. Hsieh , and R. Klasing . 2020 . Top-down construction of independent spanning trees in alternating group networks . IEEE Access 8 (2020), 112333 \u2013 112347 . J.-F. Huang, S.-S. Kao, S.-Y. Hsieh, and R. Klasing. 2020. Top-down construction of independent spanning trees in alternating group networks. IEEE Access 8 (2020), 112333\u2013112347.","journal-title":"IEEE Access"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90016-8"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00205-1"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00430-0"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90230-S"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2011.02.012"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-009-0363-9"},{"key":"e_1_3_1_68_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1023\/A:1022444205860","article-title":"Graphs  \\(S(n, k)\\)  and a variant of the Tower of Hanoi problem","volume":"47","author":"Milutinovi\u00f3 S. Klav","year":"1997","unstructured":"S. Klav \\(\\check{z}\\) ar and U. Milutinovi\u00f3 . 1997 . Graphs \\(S(n, k)\\) and a variant of the Tower of Hanoi problem . Czechoslovak Mathematical Journal 47 (1997), 95 \u2013 104 . S. Klav \\(\\check{z}\\) ar and U. Milutinovi\u00f3. 1997. Graphs \\(S(n, k)\\) and a variant of the Tower of Hanoi problem. Czechoslovak Mathematical Journal 47 (1997), 95\u2013104.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"e_1_3_1_69_2","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1002\/jgt.20107","article-title":"Crossing numbers of Sierpi\u0144ski-like graphs","volume":"50","author":"Mohar S. Klav","year":"2005","unstructured":"S. Klav \\(\\check{z}\\) ar and B. Mohar . 2005 . Crossing numbers of Sierpi\u0144ski-like graphs . Journal of Graph Theory 50 (2005), 186 \u2013 198 . S. Klav \\(\\check{z}\\) ar and B. Mohar. 2005. Crossing numbers of Sierpi\u0144ski-like graphs. Journal of Graph Theory 50 (2005), 186\u2013198.","journal-title":"Journal of Graph Theory"},{"key":"e_1_3_1_70_2","first-page":"194","article-title":"Sorting and searching","volume":"3","author":"Knuth D. E.","year":"1973","unstructured":"D. E. Knuth . 1973 . Sorting and searching . Art of Computer Programming 3 (1973), 194 \u2013 198 . D. E. Knuth. 1973. Sorting and searching. Art of Computer Programming 3 (1973), 194\u2013198.","journal-title":"Art of Computer Programming"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1189580"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2389847"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.08.023"},{"key":"e_1_3_1_74_2","first-page":"93","article-title":"Research on completely independent spanning trees based on the degree of vertices","volume":"44","author":"Lin C.-K.","year":"2017","unstructured":"C.-K. Lin , Y. Zhao , J. Fan , and B. Cheng . 2017 . Research on completely independent spanning trees based on the degree of vertices . Computer Science (Chinese) 44 , 6 (2017), 93 \u2013 96 . C.-K. Lin, Y. Zhao, J. Fan, and B. Cheng. 2017. Research on completely independent spanning trees based on the degree of vertices. Computer Science (Chinese) 44, 6 (2017), 93\u201396.","journal-title":"Computer Science (Chinese)"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.03.012"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.061"},{"key":"e_1_3_1_77_2","volume-title":"Proceedings of the 2008 2nd International Symposium on Intelligent Information Technology Application Workshop (IITA\u201908 Workshop). 1021\u20131024","author":"Ma D.","unstructured":"D. Ma and H. Liu . 2008. Two edge-disjoint Hamiltonian paths in crossed cubes . In Proceedings of the 2008 2nd International Symposium on Intelligent Information Technology Application Workshop (IITA\u201908 Workshop). 1021\u20131024 . D. Ma and H. Liu. 2008. Two edge-disjoint Hamiltonian paths in crossed cubes. In Proceedings of the 2008 2nd International Symposium on Intelligent Information Technology Application Workshop (IITA\u201908 Workshop). 1021\u20131024."},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2018.08.006"},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1806"},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000149"},{"key":"e_1_3_1_82_2","volume-title":"Proceedings of the 13th International Conference on Wireless and Mobile Computing, Networking, and Communications (WiMob\u201917)","author":"Moinet A.","unstructured":"A. Moinet , B. Darties , N. Gastineau , J.-L. Baril , and O. Togni . 2017. Completely independent spanning trees for enhancing the robustness in ad-hoc networks . In Proceedings of the 13th International Conference on Wireless and Mobile Computing, Networking, and Communications (WiMob\u201917) . 63\u201370. A. Moinet, B. Darties, N. Gastineau, J.-L. Baril, and O. Togni. 2017. Completely independent spanning trees for enhancing the robustness in ad-hoc networks. In Proceedings of the 13th International Conference on Wireless and Mobile Computing, Networking, and Communications (WiMob\u201917). 63\u201370."},{"key":"e_1_3_1_83_2","unstructured":"S. Nagai and S. Nakano. 2001. A linear-time algorithm to find independent spanning trees in maximal planar graphs. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E84-A 5 (2001) 1102\u20131109.  S. Nagai and S. Nakano. 2001. A linear-time algorithm to find independent spanning trees in maximal planar graphs. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E84-A 5 (2001) 1102\u20131109."},{"key":"e_1_3_1_84_2","unstructured":"K. Obokata Y. Iwasaki F. Bao and Y. Igarashi. 1996. Independent spanning trees of product graphs and their construction. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E79-A 11 (1996) 1894\u20131903.  K. Obokata Y. Iwasaki F. Bao and Y. Igarashi. 1996. Independent spanning trees of product graphs and their construction. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E79-A 11 (1996) 1894\u20131903."},{"key":"e_1_3_1_85_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.08.024"},{"key":"e_1_3_1_86_2","first-page":"107","article-title":"Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs","volume":"1","author":"Pai K.-J.","year":"2013","unstructured":"K.-J. Pai , S.-M. Tang , J.-M. Chang , and J.-S. Yang . 2013 . Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs . Advances in Intelligent Systems and Applications 1 (2013), 107 \u2013 113 . K.-J. Pai, S.-M. Tang, J.-M. Chang, and J.-S. Yang. 2013. Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs. Advances in Intelligent Systems and Applications 1 (2013), 107\u2013113.","journal-title":"Advances in Intelligent Systems and Applications"},{"key":"e_1_3_1_87_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105874"},{"key":"e_1_3_1_88_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2910019"},{"key":"e_1_3_1_89_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.02.007"},{"key":"e_1_3_1_90_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-020-03297-9"},{"key":"e_1_3_1_91_2","series-title":"Lecture Notes in Computer Science","volume-title":"Frontiers in Algorithmics","author":"Pai K.-J.","unstructured":"K.-J. Pai , R.-S. Chang , J.-M. Chang , and R.-Y. Wu. 2019. Constructing three completely independent spanning trees in locally twisted cubes . In Frontiers in Algorithmics . Lecture Notes in Computer Science , Vol. 11458 . Springer , 88\u201399. K.-J. Pai, R.-S. Chang, J.-M. Chang, and R.-Y. Wu. 2019. Constructing three completely independent spanning trees in locally twisted cubes. In Frontiers in Algorithmics. Lecture Notes in Computer Science, Vol. 11458. Springer, 88\u201399."},{"key":"e_1_3_1_92_2","volume-title":"Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications. 1358\u20131365","author":"Pai K.-J.","year":"2019","unstructured":"K.-J. Pai , R.-S. Chang , R.-Y. Wu , and J.-M. Chang . 2019 . Three completely independent spanning trees of crossed cubes with application to secure-protection routing . In Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications. 1358\u20131365 . K.-J. Pai, R.-S. Chang, R.-Y. Wu, and J.-M. Chang. 2019. Three completely independent spanning trees of crossed cubes with application to secure-protection routing. In Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications. 1358\u20131365."},{"key":"e_1_3_1_93_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.035"},{"key":"e_1_3_1_94_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.09.006"},{"key":"e_1_3_1_95_2","volume-title":"Completely independent spanning trees on some interconnection networks. IEICE Transactions on Information and Systems E97-D, 9","author":"Pai K.-J.","year":"2014","unstructured":"K.-J. Pai , J.-S. Yang , S.-C. Yao , S.-M. Tang , and J.-M. Chang . 2014. Completely independent spanning trees on some interconnection networks. IEICE Transactions on Information and Systems E97-D, 9 ( 2014 ), 2514\u20132517. K.-J. Pai, J.-S. Yang, S.-C. Yao, S.-M. Tang, and J.-M. Chang. 2014. Completely independent spanning trees on some interconnection networks. IEICE Transactions on Information and Systems E97-D, 9 (2014), 2514\u20132517."},{"key":"e_1_3_1_96_2","volume-title":"Proceedings of the 2017 9th IEEE International Conference on Communication Software and Networks. 1103\u20131106","author":"Pan T.","unstructured":"T. Pan , B. Cheng , J. Fan , C.-K. Lin , and D. Zhou . 2017. Toward the completely independent spanning trees problem on BCube . In Proceedings of the 2017 9th IEEE International Conference on Communication Software and Networks. 1103\u20131106 . T. Pan, B. Cheng, J. Fan, C.-K. Lin, and D. Zhou. 2017. Toward the completely independent spanning trees problem on BCube. In Proceedings of the 2017 9th IEEE International Conference on Communication Software and Networks. 1103\u20131106."},{"key":"e_1_3_1_97_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.11.023"},{"key":"e_1_3_1_98_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.11.015"},{"key":"e_1_3_1_99_2","first-page":"2130","article-title":"A unified method to construct node-independent spanning trees in a kind of data center networks","volume":"38","author":"Qian Y.","year":"2021","unstructured":"Y. Qian , B. Cheng , J. Fan , G. Chen , Y. Wang , and Y. Xiao . 2021 . A unified method to construct node-independent spanning trees in a kind of data center networks . Application Research of Computers (Chinese) 38 , 7 (2021), 2130 \u2013 2134 . Y. Qian, B. Cheng, J. Fan, G. Chen, Y. Wang, and Y. Xiao. 2021. A unified method to construct node-independent spanning trees in a kind of data center networks. Application Research of Computers (Chinese) 38, 7 (2021), 2130\u20132134.","journal-title":"Application Research of Computers (Chinese)"},{"key":"e_1_3_1_100_2","volume-title":"Proceedings of the 2021 IEEE 32nd International Conference on Application-Specific Systems, Architectures, and Processors (ASAP\u201921)","author":"Qian Y.","unstructured":"Y. Qian , B. Cheng , J. Fan , Y. Wang , and R. Jiang . 2021. Edge-disjoint spanning trees in the line graph of hypercubes . In Proceedings of the 2021 IEEE 32nd International Conference on Application-Specific Systems, Architectures, and Processors (ASAP\u201921) . 61\u201364. Y. Qian, B. Cheng, J. Fan, Y. Wang, and R. Jiang. 2021. Edge-disjoint spanning trees in the line graph of hypercubes. In Proceedings of the 2021 IEEE 32nd International Conference on Application-Specific Systems, Architectures, and Processors (ASAP\u201921). 61\u201364."},{"key":"e_1_3_1_101_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2019.06.060"},{"key":"e_1_3_1_102_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2931904"},{"key":"e_1_3_1_103_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.01.024"},{"key":"e_1_3_1_104_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2020.125900"},{"key":"e_1_3_1_105_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.compbiomed.2016.01.004","article-title":"Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees","volume":"70","author":"da Silva E. Sant\u2019Ana","year":"2016","unstructured":"E. Sant\u2019Ana da Silva and H. Pedrini . 2016 . Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees . Computers in Biology and Medicine 70 (2016), 51 \u2013 57 . E. Sant\u2019Ana da Silva and H. Pedrini. 2016. Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees. Computers in Biology and Medicine 70 (2016), 51\u201357.","journal-title":"Computers in Biology and Medicine"},{"key":"e_1_3_1_106_2","volume-title":"Proceedings of the 1977 4th Annual Symposium on Computer Architecture. 105\u2013124","author":"Sullivan H.","unstructured":"H. Sullivan , T. Bashkow , and D. Klappholz . 1977. A large scale, homogeneous, fully distributed parallel machine . In Proceedings of the 1977 4th Annual Symposium on Computer Architecture. 105\u2013124 . H. Sullivan, T. Bashkow, and D. Klappholz. 1977. A large scale, homogeneous, fully distributed parallel machine. In Proceedings of the 1977 4th Annual Symposium on Computer Architecture. 105\u2013124."},{"key":"e_1_3_1_107_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.98"},{"key":"e_1_3_1_108_2","first-page":"143","article-title":"Optimal independent spanning trees on hypercubes","volume":"20","author":"Tang S.-M.","year":"2004","unstructured":"S.-M. Tang , Y.-L. Wang , and Y.-H. Leu . 2004 . Optimal independent spanning trees on hypercubes . Journal of Information Science and Engineering 20 , 1 (2004), 143 \u2013 155 . S.-M. Tang, Y.-L. Wang, and Y.-H. Leu. 2004. Optimal independent spanning trees on hypercubes. Journal of Information Science and Engineering 20, 1 (2004), 143\u2013155.","journal-title":"Journal of Information Science and Engineering"},{"key":"e_1_3_1_109_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.05.009"},{"key":"e_1_3_1_110_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-018-1826-3"},{"key":"e_1_3_1_111_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw054"},{"key":"e_1_3_1_112_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00521-3"},{"key":"e_1_3_1_113_2","doi-asserted-by":"crossref","first-page":"2979","DOI":"10.1093\/comjnl\/bxab120","article-title":"An algorithm to construct completely-independent spanning trees in the line graphs of interconnection networks","volume":"65","author":"Wang Y.","year":"2022","unstructured":"Y. Wang , B. Cheng , J. Fan , Y. Qian , and R. Jiang . 2022 . An algorithm to construct completely-independent spanning trees in the line graphs of interconnection networks . Computer Journal 65 , 12 (2022), 2979 \u2013 2990 . Y. Wang, B. Cheng, J. Fan, Y. Qian, and R. Jiang. 2022. An algorithm to construct completely-independent spanning trees in the line graphs of interconnection networks. Computer Journal 65, 12 (2022), 2979\u20132990.","journal-title":"Computer Journal"},{"key":"e_1_3_1_114_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3077587"},{"key":"e_1_3_1_115_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.09.002"},{"key":"e_1_3_1_116_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.08.020"},{"key":"e_1_3_1_117_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.01.016"},{"key":"e_1_3_1_118_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.07.003"},{"key":"e_1_3_1_119_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.05.041"},{"key":"e_1_3_1_120_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxs157"},{"key":"e_1_3_1_121_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxv029"},{"key":"e_1_3_1_122_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2006.12.001"},{"key":"e_1_3_1_123_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20389"},{"key":"e_1_3_1_124_2","doi-asserted-by":"publisher","DOI":"10.1109\/I-SPAN.2009.55"},{"key":"e_1_3_1_125_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2367498"},{"key":"e_1_3_1_126_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.351709"},{"key":"e_1_3_1_127_2","first-page":"21","article-title":"On the independent spanning trees of recursive circulant graphs  \\(G(cd^m, d)\\)  with  \\(d\\gt 2\\)","volume":"410","author":"Yang J.-S.","year":"2009","unstructured":"J.-S. Yang , J.-M. Chang , S.-M. Tang , and Y.-L. Wang . 2009 . On the independent spanning trees of recursive circulant graphs \\(G(cd^m, d)\\) with \\(d\\gt 2\\) . Theoretical Computer Science 410 , 21 \u2013 23 (2009), 2001\u20132010. J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang. 2009. On the independent spanning trees of recursive circulant graphs \\(G(cd^m, d)\\) with \\(d\\gt 2\\) . Theoretical Computer Science 410, 21\u201323 (2009), 2001\u20132010.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_1_128_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007143"},{"key":"e_1_3_1_129_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.04.014"},{"key":"e_1_3_1_130_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1346-z"},{"key":"e_1_3_1_131_2","volume-title":"Constructing two completely independent spanning trees in balanced hypercubes. IEICE Transactions on Information and Systems E102D, 12","author":"Yang Y.-X.","year":"2019","unstructured":"Y.-X. Yang , K.-J. Pai , R.-S. Chang , and J.-M. Chang . 2019. Constructing two completely independent spanning trees in balanced hypercubes. IEICE Transactions on Information and Systems E102D, 12 ( 2019 ), 2409\u20132412. Y.-X. Yang, K.-J. Pai, R.-S. Chang, and J.-M. Chang. 2019. Constructing two completely independent spanning trees in balanced hypercubes. IEICE Transactions on Information and Systems E102D, 12 (2019), 2409\u20132412."},{"key":"e_1_3_1_132_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130205"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:30Z","timestamp":1750178250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,17]]},"references-count":131,"journal-issue":{"issue":"14s","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3591110"],"URL":"https:\/\/doi.org\/10.1145\/3591110","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,17]]},"assertion":[{"value":"2022-02-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}