{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T09:15:41Z","timestamp":1790500541459,"version":"4.1.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["107-2221-E-131-011"],"award-info":[{"award-number":["107-2221-E-131-011"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["107-2221-E-141-001-MY3"],"award-info":[{"award-number":["107-2221-E-141-001-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10878-019-00430-0","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T16:02:43Z","timestamp":1560182563000},"page":"972-986","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks"],"prefix":"10.1007","volume":"38","author":[{"given":"Shih-Shun","family":"Kao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kung-Jui","family":"Pai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ro-Yu","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9542-7968","authenticated-orcid":false,"given":"Jou-Ming","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,10]]},"reference":[{"key":"430_CR1","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1109\/12.21148","volume":"38","author":"SB Akers","year":"1989","unstructured":"Akers SB, Krishnamurty B (1989) A group theoretic model for symmetric interconnection networks. IEEE Trans Comput 38:555\u2013566","journal-title":"IEEE Trans Comput"},{"key":"430_CR2","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.ins.2007.01.017","volume":"177","author":"T Araki","year":"2007","unstructured":"Araki T, Kikuchi Y (2007) Hamiltonian laceability of bubble-sort graphs with edge faults. Inf Sci 177:2679\u20132691","journal-title":"Inf Sci"},{"key":"430_CR3","unstructured":"Bao F, Funyu Y, Hamada Y, Igarashi Y (1997) Reliable broadcasting and secure distributing in channel networks. In: Proceedings of 3rd international symposium on parallel architectures, algorithms and networks (I-SPAN\u201997), pp 472\u2013478"},{"key":"430_CR4","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1007\/s10878-016-0018-8","volume":"33","author":"Y-H Chang","year":"2017","unstructured":"Chang Y-H, Yang J-S, Hsieh S-Y, Chang J-M, Wang Y-L (2017a) Construction independent spanning trees on locally twisted cubes in parallel. J Comb Optim 33:956\u2013967","journal-title":"J Comb Optim"},{"key":"430_CR5","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.dam.2016.11.017","volume":"219","author":"J-M Chang","year":"2017","unstructured":"Chang J-M, Yang T-J, Yang J-S (2017b) A parallel algorithm for constructing independent spanning trees in twisted cubes. Discrete Appl Math 219:74\u201382","journal-title":"Discrete Appl Math"},{"key":"430_CR6","unstructured":"Chen X, Fan J, Lin C-K, Cheng B, Liu Z (2015) A VoD system model based on BC graphs. In: Proceedings of 4th national conference on electrical, electronics and computer engineering (NCEECE 2015), Xian, China, December 12\u201313, pp 1499\u20131505"},{"key":"430_CR7","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1016\/j.future.2018.02.010","volume":"87","author":"B Cheng","year":"2018","unstructured":"Cheng B, Fan J, Lyu Q, Zhou J, Liu Z (2018) Constructing independent spanning trees with height $$n$$ on the $$n$$-dimensional crossed cube. Future Gener Comput Syst 87:404\u2013415","journal-title":"Future Gener Comput Syst"},{"key":"430_CR8","doi-asserted-by":"publisher","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:507\u2013537","journal-title":"J Algorithms"},{"key":"430_CR9","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0020-0190(95)00162-1","volume":"56","author":"W-K Chiang","year":"1995","unstructured":"Chiang W-K, Chen R-J (1995) The$$(n, k)$$-star graph: a generalized star graph. Inf Process Lett 56:259\u2013264","journal-title":"Inf Process Lett"},{"key":"430_CR10","doi-asserted-by":"publisher","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:1023\u20131058","journal-title":"SIAM J Comput"},{"key":"430_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.compbiomed.2016.01.004","volume":"70","author":"ESA da Silva","year":"2016","unstructured":"da Silva ESA, Pedrini H (2016a) Inferring patterns in mitochondrial DNA sequences through hypercube independent spanning trees. Comput Biol Med 70:51\u201357","journal-title":"Comput Biol Med"},{"key":"430_CR12","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.eswa.2016.06.002","volume":"61","author":"ESA da Silva","year":"2016","unstructured":"da Silva ESA, Pedrini H (2016b) Connected-component labeling based on hypercubes for memory constrained scenarios. Expert Syst Appl 61:272\u2013281","journal-title":"Expert Syst Appl"},{"key":"430_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0020-0190(92)90030-Y","volume":"42","author":"K Day","year":"1992","unstructured":"Day K, Tripathi A (1992) Arrangement graphs: a class of generalized star graphs. Inf Process Lett 42:235\u2013241","journal-title":"Inf Process Lett"},{"key":"430_CR14","unstructured":"Guo C, Lu G, Xiong Y, Cao J, Zhu Y, Chen C, Zhang Y (2011) Datacast: a scalable and efficient group data delivery service for data centers. Report MSR-TR-2011-76 from Microsoft Research Asia"},{"key":"430_CR15","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2016.02.024","volume":"627","author":"R-X Hao","year":"2012","unstructured":"Hao R-X, Tian Z-X, Xu J-M (2012) Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs. Theor Comput Sci 627:36\u201353","journal-title":"Theor Comput Sci"},{"key":"430_CR16","unstructured":"IEEE (2006) 802.1s\u2014multiple spanning trees. \n                    http:\/\/www.ieee802.org\/1\/pages\/802.1s.html\n                    \n                  . Accessed 8 June 2019"},{"key":"430_CR17","doi-asserted-by":"publisher","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:43\u201359","journal-title":"Inf Comput"},{"key":"430_CR18","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1109\/12.29465","volume":"38","author":"SL Johnsson","year":"1989","unstructured":"Johnsson SL, Ho C-T (1989) Optimum broadcasting and personalized communication in hypercubes. IEEE Trans Comput 38:1249\u20131268","journal-title":"IEEE Trans Comput"},{"key":"430_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1002\/net.3230230414","volume":"23","author":"J Jwo","year":"1993","unstructured":"Jwo J, Lakshmivarahan S, Dhall SK (1993) A new class of interconnection networks based on the alternating group. Networks 23:315\u2013326","journal-title":"Networks"},{"key":"430_CR20","unstructured":"Kao S-S, Chang J-M, Pai K-J, Yang J-S, Tang S-M, Wu R-Y (2017) A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks. In: Proceedings of 11th international conference on combinatorial optimization and applications (COCOA 2017), Shanghai, December 16\u201318, vol 10627. LNCS, pp 472\u2013478"},{"key":"430_CR21","unstructured":"Kao S-S, Chang J-M, Pai K-J, Wu R-Y (2018) Open source for \u201cConstructing independent spanning trees on bubble-sort networks\u201d. \n                    https:\/\/sites.google.com\/ntub.edu.tw\/ist-bs\/\n                    \n                  . Accessed 8 Aug 2018"},{"key":"430_CR22","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.ipl.2006.05.012","volume":"100","author":"Y Kikuchi","year":"2006","unstructured":"Kikuchi Y, Araki T (2006) Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Inf Process Lett 100:52\u201359","journal-title":"Inf Process Lett"},{"key":"430_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2017.01.021","volume":"670","author":"T-L Kung","year":"2017","unstructured":"Kung T-L, Hung C-N (2017) Estimating the subsystem reliability of bubblesort networks. Theor Comput Sci 670:45\u201355","journal-title":"Theor Comput Sci"},{"key":"430_CR24","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0167-8191(93)90054-O","volume":"19","author":"S Lakshmivarahan","year":"1993","unstructured":"Lakshmivarahan S, Jwo J, Dhall SK (1993) Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey. Parallel Comput 19:361\u2013407","journal-title":"Parallel Comput"},{"key":"430_CR25","doi-asserted-by":"publisher","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"},{"key":"430_CR26","doi-asserted-by":"crossref","unstructured":"Sharma S, Gopalan K, Nanda S, Chiueh T (2004) Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks. In: Proceedings of 23rd annual joint conference of the IEEE computer and communications societies (INFOCOM\u201904), Hong Kong, China, March 7\u201311, pp 1408\u20131417","DOI":"10.1109\/INFCOM.2004.1354651"},{"key":"430_CR27","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1002\/scj.20518","volume":"37","author":"Y Suzuki","year":"2006","unstructured":"Suzuki Y, Kaneko K (2006) An algorithm for disjoint paths in bubble-sort graphs. Syst Comput Jpn 37:27\u201332","journal-title":"Syst Comput Jpn"},{"key":"430_CR28","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1093\/ietisy\/e91-d.4.1003","volume":"E91\u2013D","author":"Y Suzuki","year":"2008","unstructured":"Suzuki Y, Kaneko K (2008) The container problem in bubble-sort graphs. IEICE Trans Inf Syst E91\u2013D:1003\u20131009","journal-title":"IEICE Trans Inf Syst"},{"key":"430_CR29","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2011.11.016","volume":"421","author":"S Wang","year":"2012","unstructured":"Wang S, Yang Y (2012) Fault tolerance in bubble-sort graph networks. Theor Comput Sci 421:62\u201369","journal-title":"Theor Comput Sci"},{"key":"430_CR30","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1080\/00207160.2015.1119817","volume":"94","author":"M Wang","year":"2017","unstructured":"Wang M, Guo Y, Wang S (2017) The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Int J Comput Math 94:620\u2013631","journal-title":"Int J Comput Math"},{"key":"430_CR31","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2016.03.019","volume":"628","author":"M Wang","year":"2016","unstructured":"Wang M, Lin Y, Wang S (2016) The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Theor Comput Sci 628:92\u2013100","journal-title":"Theor Comput Sci"},{"key":"430_CR32","doi-asserted-by":"publisher","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. Discrete Appl Math 159:1254\u20131263","journal-title":"Discrete Appl Math"},{"key":"430_CR33","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1016\/j.ipl.2015.06.011","volume":"115","author":"Y Yang","year":"2015","unstructured":"Yang Y, Wang S, Li J (2015) Subnetwork preclusion for bubble-sort graph networks. Inf Process Lett 115:817\u2013821","journal-title":"Inf Process Lett"},{"key":"430_CR34","doi-asserted-by":"publisher","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:175\u2013188","journal-title":"J Graph Theory"},{"key":"430_CR35","first-page":"53","volume":"180","author":"S Zhou","year":"2013","unstructured":"Zhou S, Wang J, Xu X, Xu J-M (2013) Conditional fault diagnosis of bubble sort graphs under the PMC model. Intell Comput Evol Comput AISC 180:53\u201359","journal-title":"Intell Comput Evol Comput AISC"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00430-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00430-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00430-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,8]],"date-time":"2020-06-08T23:07:16Z","timestamp":1591657636000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00430-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,10]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["430"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00430-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,10]]},"assertion":[{"value":"10 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}