{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T09:15:45Z","timestamp":1790500545049,"version":"4.1.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,4,30]],"date-time":"2016-04-30T00:00:00Z","timestamp":1461974400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Parallel Construction of Independent Spanning Trees on Enhanced Hypercubes","award":["MOST103-2221-E-141-003"],"award-info":[{"award-number":["MOST103-2221-E-141-003"]}]},{"name":"Completely Independent Spanning Trees on Some Interconnection Networks","award":["MOST103-2221-E-001"],"award-info":[{"award-number":["MOST103-2221-E-001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s10878-016-0018-8","type":"journal-article","created":{"date-parts":[[2016,4,30]],"date-time":"2016-04-30T02:06:43Z","timestamp":1461982003000},"page":"956-967","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Construction independent spanning trees on locally twisted cubes in parallel"],"prefix":"10.1007","volume":"33","author":[{"given":"Yu-Huei","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinn-Shyong","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jou-Ming","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yue-Li","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,30]]},"reference":[{"key":"18_CR1","unstructured":"Bao F, Funyu Y, Hamada Y, Igarashi Y et\u00a0al (1998) Reliable broadcasting and secure distributing in channel networks. IEICE Trans Fundam Electron Commun Comput Sci E81\u2013A(5):796\u2013806"},{"key":"18_CR2","first-page":"607","volume":"36","author":"Q-Y Chang","year":"2006","unstructured":"Chang Q-Y, Ma M-J, Xu J-M (2006) Fault-tolerant pancyclicity of locally twisted cubes (in Chinese). J China Univ Sci Tech 36:607\u2013610","journal-title":"J China Univ Sci Tech"},{"issue":"12","key":"18_CR3","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1016\/j.ipl.2014.06.015","volume":"114","author":"J-M Chang","year":"2014","unstructured":"Chang J-M, Wang J-D, Yang J-S, Pai K-J (2014) A comment on Independent spanning trees in crossed cubes. Inf Process Lett 114(12):734\u2013739","journal-title":"Inf Process Lett"},{"issue":"5","key":"18_CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.ipl.2010.11.018","volume":"111","author":"X-B Chen","year":"2011","unstructured":"Chen X-B (2011) Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs. Inf Process Lett 111(5):235\u2013238","journal-title":"Inf Process Lett"},{"issue":"3","key":"18_CR5","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1007\/s11227-013-0883-1","volume":"65","author":"B Cheng","year":"2013","unstructured":"Cheng B, Fan J, Jia X, Jia J (2013a) Parallel construction of independent spanning trees and an application in diagnosis on M\u00f6bius cubes. J Supercomput 65(3):1279\u20131301","journal-title":"J Supercomput"},{"issue":"5","key":"18_CR6","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.jpdc.2013.01.009","volume":"73","author":"B Cheng","year":"2013","unstructured":"Cheng B, Fan J, Jia X, Wang J (2013b) Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes. J Parallel Distrib Comput 73(5):641\u2013652","journal-title":"J Parallel Distrib Comput"},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1016\/j.ins.2013.01.010","volume":"233","author":"B Cheng","year":"2013","unstructured":"Cheng B, Fan J, Jia X, Zhang S (2013c) Independent spanning trees in crossed cubes. Inf Sci 233:276\u2013289","journal-title":"Inf Sci"},{"issue":"11","key":"18_CR8","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1093\/comjnl\/bxs123","volume":"56","author":"B Cheng","year":"2013","unstructured":"Cheng B, Fan J, Jia X, Zhang S, Chen B (2013d) Constructive algorithm of independent spanning trees on M\u00f6bius cubes. Comput J 56(11):1347\u20131362","journal-title":"Comput J"},{"issue":"1","key":"18_CR9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/TPDS.2014.2307871","volume":"26","author":"B Cheng","year":"2015","unstructured":"Cheng B, Fan J, Jia X (2015) Dimensional-permutation-based independent spanning trees in bijective connection networks. IEEE Trans Parallel Distrib Syst 26(1):45\u201353","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"4","key":"18_CR10","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1016\/0196-6774(88)90015-6","volume":"9","author":"J Cheriyan","year":"1988","unstructured":"Cheriyan J, Maheshwari SN (1988) Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J Algorithms 9(4):507\u2013537","journal-title":"J Algorithms"},{"issue":"5","key":"18_CR11","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1137\/S0097539703436734","volume":"35","author":"S Curran","year":"2006","unstructured":"Curran S, Lee O, Yu X (2006) Finding four independent trees. SIAM J Comput 35(5):1023\u20131058","journal-title":"SIAM J Comput"},{"issue":"19","key":"18_CR12","doi-asserted-by":"crossref","first-page":"3794","DOI":"10.1016\/j.ins.2010.06.001","volume":"180","author":"Y Han","year":"2010","unstructured":"Han Y, Fan J, Zhang S, Yang J, Qjan P (2010) Embedding meshes into locally twisted cubes. Inf Sci 180(19):3794\u20133805","journal-title":"Inf Sci"},{"issue":"8\u201310","key":"18_CR13","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1016\/j.tcs.2008.12.025","volume":"410","author":"S-Y Hsieh","year":"2009","unstructured":"Hsieh S-Y, Tu C-J (2009) Constructing edge-disjoint spanning trees in locally twisted cubes. Theor Comput Sci 410(8\u201310):926\u2013932","journal-title":"Theor Comput Sci"},{"issue":"1","key":"18_CR14","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/s10878-008-9157-x","volume":"19","author":"S-Y Hsieh","year":"2010","unstructured":"Hsieh S-Y, Wu C-Y (2010) Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults. J Combin Optim 19(1):16\u201330","journal-title":"J Combin Optim"},{"issue":"1","key":"18_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ipl.2006.10.008","volume":"102","author":"KS Hu","year":"2007","unstructured":"Hu KS, Yeoh S-S, Chen C, Hsu L-H (2007) Node-pancyclicity and edge-pancyclicity of hypercube variants. Inf Process Lett 102(1):1\u20137","journal-title":"Inf Process Lett"},{"issue":"1","key":"18_CR16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01202468","volume":"10","author":"A Huck","year":"1994","unstructured":"Huck A (1994) Independent trees in graphs. Graphs Comb 10(1):29\u201345","journal-title":"Graphs Comb"},{"issue":"1","key":"18_CR17","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01202468","volume":"15","author":"A Huck","year":"1999","unstructured":"Huck A (1999) Independent trees in planar graphs. Graphs Comb 15(1):29\u201377","journal-title":"Graphs Comb"},{"issue":"1","key":"18_CR18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0890-5401(88)90016-8","volume":"79","author":"A Itai","year":"1988","unstructured":"Itai A, Rodeh M (1988) The multi-tree approach to reliability in distributed networks. Inf Comput 79(1):43\u201359","journal-title":"Inf Comput"},{"issue":"3","key":"18_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0020-0190(98)00205-1","volume":"69","author":"Y Iwasaki","year":"1999","unstructured":"Iwasaki Y, Kajiwara Y, Obokata K, Igarashi Y (1999) Independent spanning trees of chordal rings. Inf Process Lett 69(3):155\u2013160","journal-title":"Inf Process Lett"},{"issue":"2","key":"18_CR20","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/s11227-009-0363-9","volume":"56","author":"J-S Kim","year":"2011","unstructured":"Kim J-S, Lee H-O, Cheng E, Lipt\u00e1k L (2011a) Optimal independent spanning trees on odd graphs. J Supercomput 56(2):212\u2013225","journal-title":"J Supercomput"},{"issue":"13","key":"18_CR21","doi-asserted-by":"crossref","first-page":"2892","DOI":"10.1016\/j.ins.2011.02.012","volume":"181","author":"J-S Kim","year":"2011","unstructured":"Kim J-S, Lee H-O, Cheng E, Lipt\u00e1k L (2011b) Independent spanning trees on even networks. Inf Sci 181(13):2892\u20132905","journal-title":"Inf Sci"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Lin J-C, Yang J-S, Hsu C-C, Chang J-M (2010) Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes. Inf Process Lett 110(10):414\u2013419","DOI":"10.1016\/j.ipl.2010.03.012"},{"issue":"22","key":"18_CR23","doi-asserted-by":"crossref","first-page":"2237","DOI":"10.1016\/j.tcs.2010.12.061","volume":"412","author":"Y-J Liu","year":"2011","unstructured":"Liu Y-J, Lan JK, Chou WY, Chen C (2011) Constructing independent spanning trees for locally twisted cubes. Theor Comput Sci 412(22):2237\u20132252","journal-title":"Theor Comput Sci"},{"issue":"7","key":"18_CR24","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1016\/j.aml.2005.08.021","volume":"19","author":"M-J Ma","year":"2006","unstructured":"Ma M-J, Xu J-M (2006) Panconnectivity of locally twisted cubes. Appl Math Lett 19(7):673\u2013677","journal-title":"Appl Math Lett"},{"key":"18_CR25","first-page":"89","volume":"89","author":"M-J Ma","year":"2008","unstructured":"Ma M-J, Xu J-M (2008) Weak edge-pancyclicity of locally twisted cubes. Ars Comb 89:89\u201394","journal-title":"Ars Comb"},{"issue":"2","key":"18_CR26","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1142\/S0129054199000149","volume":"10","author":"K Miura","year":"1999","unstructured":"Miura K, Nakano S, Nishizeki T, Takahashi D (1999) A linear-time algorithm to find four independent spanning trees in four connected planar graphs. Int J Found Comput Sci 10(2):195\u2013210","journal-title":"Int J Found Comput Sci"},{"key":"18_CR27","unstructured":"Nagai S, Nakano S (2001) A linear-time algorithm to find independent spanning trees in maximal planar graphs. IEICE Trans Fundam Electron Commun Comput Sci E84\u2013A(5):1102\u20131109"},{"key":"18_CR28","unstructured":"Obokata K, Iwasaki Y, Bao F, Igarashi Y (1996) Independent spanning trees of product graphs and their construction. IEICE Trans Fundam Electron Commun Comput Sci E79\u2013A(11):1894\u20131903"},{"key":"18_CR29","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/j.tcs.2007.02.029","volume":"377","author":"J-H Park","year":"2007","unstructured":"Park J-H, Lim H-S, Kim H-C (2007) Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. Theor Comput Sci 377:170\u2013180","journal-title":"Theor Comput Sci"},{"key":"18_CR30","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0020-0255(01)00121-9","volume":"137","author":"AA Rescigno","year":"2001","unstructured":"Rescigno AA (2001) Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security. Inf Sci 137:259\u2013276","journal-title":"Inf Sci"},{"issue":"1","key":"18_CR31","first-page":"143","volume":"20","author":"S-M Tang","year":"2004","unstructured":"Tang S-M, Wang Y-L, Leu Y-H (2004) Optimal independent spanning trees on hypercubes. J Inf Sci Eng 20(1):143\u2013155","journal-title":"J Inf Sci Eng"},{"issue":"1","key":"18_CR32","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.2009.98","volume":"59","author":"S-M Tang","year":"2010","unstructured":"Tang S-M, Yang J-S, Wang Y-L, Chang J-M (2010) Independent spanning trees on multidimensional torus networks. IEEE Trans Comput 59(1):93\u2013102","journal-title":"IEEE Trans Comput"},{"issue":"1","key":"18_CR33","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jpdc.2011.09.002","volume":"72","author":"Y Wang","year":"2012","unstructured":"Wang Y, Fan J, Zhou G, Jia X (2012a) Independent spanning trees on twisted cubes. J Parallel Distrib Comput 72(1):58\u201369","journal-title":"J Parallel Distrib Comput"},{"key":"18_CR34","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.tcs.2012.08.020","volume":"465","author":"Y Wang","year":"2012","unstructured":"Wang Y, Fan J, Jia X, Huang H (2012b) An algorithm to construct independent spanning trees on parity cubes. Theor Comput Sci 465:61\u201372","journal-title":"Theor Comput Sci"},{"issue":"12","key":"18_CR35","doi-asserted-by":"crossref","first-page":"1713","DOI":"10.1016\/j.jpdc.2012.07.003","volume":"72","author":"J Werapun","year":"2012","unstructured":"Werapun J, Intakosum S, Boonjing V (2012) An efficient parallel construction of optimal independent spanning trees on hypercubes. J Parallel Distrib Comput 72(12):1713\u20131724","journal-title":"J Parallel Distrib Comput"},{"issue":"11","key":"18_CR36","doi-asserted-by":"crossref","first-page":"2268","DOI":"10.1016\/j.ins.2011.01.031","volume":"181","author":"X Xu","year":"2011","unstructured":"Xu X, Zhai W, Xu J-M, Deng A, Yang Y (2011) Fault-tolerant edge-pancyclicity of locally twisted cubes. Inf Sci 181(11):2268\u20132277","journal-title":"Inf Sci"},{"issue":"4","key":"18_CR37","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1002\/net.20389","volume":"56","author":"J-S Yang","year":"2010","unstructured":"Yang J-S, Chang J-M (2010) Independent spanning trees on folded hyper-stars. Networks 56(4):272\u2013281","journal-title":"Networks"},{"issue":"1","key":"18_CR38","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1093\/comjnl\/bxs157","volume":"57","author":"J-S Yang","year":"2014","unstructured":"Yang J-S, Chang J-M (2014) Optimal independent spanning trees on Cartesian product of hybrid graphs. Comput J 57(1):93\u201399","journal-title":"Comput J"},{"issue":"6","key":"18_CR39","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1016\/j.camwa.2006.09.008","volume":"53","author":"H Yang","year":"2007","unstructured":"Yang H, Yang X (2007) A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM $$^*$$ \u2217 model. Comput Math Appl 53(6):918\u2013926","journal-title":"Comput Math Appl"},{"issue":"12","key":"18_CR40","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1016\/j.dam.2011.04.014","volume":"159","author":"J-S Yang","year":"2011","unstructured":"Yang J-S, Chan H-C, Chang J-M (2011) Broadcasting secure messages via optimal independent spanning trees in folded hypercubes. Discret Appl Math 159(12):1254\u20131263","journal-title":"Discret Appl Math"},{"issue":"5","key":"18_CR41","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TPDS.2007.351709","volume":"18","author":"J-S Yang","year":"2007","unstructured":"Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2007) Reducing the height of independent spanning trees in chordal rings. IEEE Trans Parallel Distrib Syst 18(5):644\u2013657","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"21\u201323","key":"18_CR42","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1016\/j.tcs.2008.12.042","volume":"410","author":"J-S Yang","year":"2009","unstructured":"Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2009) On the independent spanning trees of recursive circulant graphs $$G(cd^m, d)$$ G ( c d m , d ) with $$d>2$$ d > 2 . Theor Comput Sci 410(21\u201323):2001\u20132010","journal-title":"Theor Comput Sci"},{"issue":"1","key":"18_CR43","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1142\/S0129054110007143","volume":"21","author":"J-S Yang","year":"2010","unstructured":"Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2010) Constructing multiple independent spanning trees on recursive circulant graphs $$G(2^m,2)$$ G ( 2 m , 2 ) . Int J Found Comput Sci 21(1):73\u201390","journal-title":"Int J Found Comput Sci"},{"key":"18_CR44","doi-asserted-by":"crossref","unstructured":"Yang J-S, Chang J-M, Pai K-J, Chan H-C (2015a) Parallel construction of independent spanning trees on enhanced hypercubes. IEEE Trans Parallel Distrib Syst 26(11):3090\u20133098","DOI":"10.1109\/TPDS.2014.2367498"},{"issue":"4","key":"18_CR45","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1080\/0020716042000301752","volume":"82","author":"X Yang","year":"2005","unstructured":"Yang X, Evans DJ, Megson GM (2005) The locally twisted cubes. Int J Comput Math 82(4):401\u2013413","journal-title":"Int J Comput Math"},{"issue":"8","key":"18_CR46","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1016\/j.aml.2003.10.009","volume":"17","author":"X Yang","year":"2004","unstructured":"Yang X, Megson GM, Evans DJ (2004) Locally twisted cubes are 4-pancyclic. Appl Math Lett 17(8):919\u2013925","journal-title":"Appl Math Lett"},{"issue":"1","key":"18_CR47","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.parco.2006.12.001","volume":"33","author":"J-S Yang","year":"2007","unstructured":"Yang J-S, Tang S-M, Chang J-M, Wang Y-L (2007) Parallel construction of optimal independent spanning trees on hypercubes. Parallel Comput 33(1):73\u201379","journal-title":"Parallel Comput"},{"key":"18_CR48","doi-asserted-by":"crossref","unstructured":"Yang J-S, Wu M-R, Chang J-M, Chang Y-H (2015b) A fully parallelized scheme of constructing independent spanning trees on M\u00f6bius cubes. J Supercomput 71(3):952\u2013965","DOI":"10.1007\/s11227-014-1346-z"},{"issue":"2","key":"18_CR49","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1002\/jgt.3190130205","volume":"13","author":"A Zehavi","year":"1989","unstructured":"Zehavi A, Itai A (1989) Three tree-paths. J Graph Theory 13(2):175\u2013188","journal-title":"Three tree-paths. J Graph Theory"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0018-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0018-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0018-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0018-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T01:23:26Z","timestamp":1567819406000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0018-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,30]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["18"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0018-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,30]]}}}