{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T14:34:34Z","timestamp":1784644474125,"version":"3.55.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T00:00:00Z","timestamp":1588550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T00:00:00Z","timestamp":1588550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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-002"],"award-info":[{"award-number":["107-2221-E-141-002"]}],"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 Supercomput"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s11227-020-03297-9","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T14:03:57Z","timestamp":1588601037000},"page":"990-1014","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Constructing dual-CISTs of pancake graphs and performance assessment of protection routings on some Cayley networks"],"prefix":"10.1007","volume":"77","author":[{"given":"Kung-Jui","family":"Pai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruay-Shiung","family":"Chang","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":[[2020,5,4]]},"reference":[{"issue":"3","key":"3297_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1002\/jgt.21780","volume":"77","author":"T Araki","year":"2014","unstructured":"Araki T (2014) Dirac\u2019s condition for completely independent spanning trees. J Graph Theory 77(3):171\u2013179","journal-title":"J Graph Theory"},{"issue":"3","key":"3297_CR2","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s002240000089","volume":"31","author":"A Bouabdallah","year":"1998","unstructured":"Bouabdallah A, Heydemann MC, Opatrny J, Sotteau D (1998) Embedding complete binary trees into star and pancake graphs. Theor Comput Syst 31(3):279\u2013305","journal-title":"Theor Comput Syst"},{"issue":"8","key":"3297_CR3","doi-asserted-by":"publisher","first-page":"1556","DOI":"10.1016\/j.jcss.2015.02.003","volume":"81","author":"L Bulteau","year":"2015","unstructured":"Bulteau L, Fertin G, Rusu I (2015) Pancake flipping is hard. J Comput Syst Sci 81(8):1556\u20131574","journal-title":"J Comput Syst Sci"},{"issue":"10","key":"3297_CR4","doi-asserted-by":"publisher","first-page":"2191","DOI":"10.1587\/transfun.E98.A.2191","volume":"E98\u2013A","author":"H-Y Chang","year":"2015","unstructured":"Chang H-Y, Wang H-L, Yang J-S, Chang J-M (2015) A note on the degree condition of completely independent spanning trees. IEICE Trans Fundam Electron Commun Comput Sci E98\u2013A(10):2191\u20132193","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"issue":"9","key":"3297_CR5","doi-asserted-by":"publisher","first-page":"1932","DOI":"10.1587\/transfun.E100.A.1932","volume":"E100\u2013A","author":"J-M Chang","year":"2017","unstructured":"Chang J-M, Chang H-Y, Wang H-L, Pai K-J, Yang J-S (2017) Completely independent spanning trees on 4-regular chordal rings. IEICE Trans Fundam Electron Commun Comput Sci E100\u2013A(9):1932\u20131935","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"key":"3297_CR6","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.dam.2016.11.019","volume":"219","author":"B Cheng","year":"2017","unstructured":"Cheng B, Wang D, Fan J (2017) Constructing completely independent spanning trees in crossed cubes. Discrete Appl Math 219:100\u2013109","journal-title":"Discrete Appl Math"},{"issue":"36","key":"3297_CR7","doi-asserted-by":"publisher","first-page":"3372","DOI":"10.1016\/j.tcs.2008.04.045","volume":"410","author":"B Chitturi","year":"2009","unstructured":"Chitturi B, Fahle W, Meng Z, Morales L, Shields CO, Sudborough IH, Voit W (2009) An $$(18\/11)n$$ upper bound for sorting by prefix reversals. Theor Comput Sci 410(36):3372\u20133390","journal-title":"Theor Comput Sci"},{"issue":"2","key":"3297_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.dam.2016.09.007","volume":"217","author":"B Darties","year":"2017","unstructured":"Darties B, Gastineau N, Togni O (2017) Completely independent spanning trees in some regular graphs. Discrete Appl Math 217(2):163\u2013174","journal-title":"Discrete Appl Math"},{"key":"3297_CR9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.dam.2014.06.002","volume":"177","author":"G Fan","year":"2014","unstructured":"Fan G, Hong Y, Liu Q (2014) Ore\u2019s condition for completely independent spanning trees. Discrete Appl Math 177:95\u2013100","journal-title":"Discrete Appl Math"},{"issue":"1\u20134","key":"3297_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0020-0255(00)00021-9","volume":"126","author":"W-C Fang","year":"2000","unstructured":"Fang W-C, Hsu C-C (2000) On the fault-tolerant embedding of complete binary trees in the pancake graph interconnection network. Inf Sci 126(1\u20134):191\u2013204","journal-title":"Inf Sci"},{"key":"3297_CR11","unstructured":"Fei A, Cui J, Gerla M, Cavendish D (2001) A dual-tree scheme for fault-tolerant multicast. In: Proceedings of IEEE International Conference on Communications (ICC 2001) Helsinki, Finland, 11\u201314 June, pp 690\u2013694"},{"issue":"1","key":"3297_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"WH Gates","year":"1979","unstructured":"Gates WH, Papadimitriou CH (1979) Bounds for sorting by prefix reversal. Discrete Math 27(1):47\u201357","journal-title":"Discrete Math"},{"key":"3297_CR13","doi-asserted-by":"crossref","unstructured":"Hasunuma T (2002) Completely independent spanning trees in maximal planar graphs. In: Proceedings of 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002). Lecture Notes in Computer Science, vol 2573, pp 235\u2013245","DOI":"10.1007\/3-540-36379-3_21"},{"issue":"1\u20133","key":"3297_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0012-365X(00)00377-0","volume":"234","author":"T Hasunuma","year":"2001","unstructured":"Hasunuma T (2001) Completely independent spanning trees in the underlying graph of a line digraph. Discrete Math 234(1\u20133):149\u2013157","journal-title":"Discrete Math"},{"key":"3297_CR15","doi-asserted-by":"crossref","unstructured":"Hasunuma T (2016) Minimum degree conditions and optimal graphs for completely independent spanning trees. In: Proceedings of 26th International Workshop on Combinatorial Algorithms (IWOCA 2016). Lecture Notes in Computer Science, vol 9538, pp 260\u2013273","DOI":"10.1007\/978-3-319-29516-9_22"},{"issue":"1","key":"3297_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.20460","volume":"60","author":"T Hasunuma","year":"2012","unstructured":"Hasunuma T, Morisaka C (2012) Completely independent spanning trees in torus networks. Networks 60(1):59\u201369","journal-title":"Networks"},{"issue":"1","key":"3297_CR17","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1006\/jagm.1997.0874","volume":"25","author":"MH Heydari","year":"1997","unstructured":"Heydari MH, Sudborough IH (1997) On the diameter of the pancake network. J Algorithms 25(1):67\u201394","journal-title":"J Algorithms"},{"issue":"3","key":"3297_CR18","doi-asserted-by":"publisher","first-page":"801","DOI":"10.7151\/dmgt.2038","volume":"38","author":"X Hong","year":"2018","unstructured":"Hong X (2018) Completely independent spanning trees in $$k$$-th power of graphs. Discuss Math Graph Theory 38(3):801\u2013810","journal-title":"Discuss Math Graph Theory"},{"issue":"10","key":"3297_CR19","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/j.ipl.2016.05.004","volume":"116","author":"X Hong","year":"2016","unstructured":"Hong X, Liu Q (2016) Degree condition for completely independent spanning trees. Inf Process Lett 116(10):644\u2013648","journal-title":"Inf Process Lett"},{"issue":"5","key":"3297_CR20","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0020-0190(02)00510-0","volume":"86","author":"C-N Hung","year":"2003","unstructured":"Hung C-N, Hsu H-C, Liang K-Y, Hsu L-H (2003) Ring embedding in faulty pancake graphs. Inf Process Lett 86(5):271\u2013275","journal-title":"Inf Process Lett"},{"key":"3297_CR21","doi-asserted-by":"crossref","unstructured":"Ishida K, Kakuda Y, Kikuno T (1995) A routing protocol for finding two node disjoint paths in computer networks. In: Proceedings of International Conference on Network Protocols (ICNP), Tokyo, Japan, 7\u201310 Nov, pp 340\u2013347","DOI":"10.1109\/ICNP.1995.524850"},{"issue":"9","key":"3297_CR22","first-page":"1628","volume":"E86\u2013D","author":"K Kaneko","year":"2003","unstructured":"Kaneko K, Suzuki Y (2003) Node-to-set disjoint paths problem in pancake graphs. IEICE Trans Inf Syst E86\u2013D(9):1628\u20131633","journal-title":"IEICE Trans Inf Syst"},{"issue":"6","key":"3297_CR23","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/0167-8191(94)00096-S","volume":"21","author":"A Kanevsky","year":"1995","unstructured":"Kanevsky A, Feng C (1995) On the embedding of cycles in pancake graphs. Parallel Comput 21(6):923\u2013936","journal-title":"Parallel Comput"},{"issue":"3","key":"3297_CR24","doi-asserted-by":"publisher","first-page":"777","DOI":"10.7151\/dmgt.1978","volume":"37","author":"E Konstantinova","year":"2017","unstructured":"Konstantinova E (2017) Chromatic properties of the pancake graphs. Discuss Math Graph Theory 37(3):777\u2013787","journal-title":"Discuss Math Graph Theory"},{"issue":"5","key":"3297_CR25","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1109\/TNET.2011.2123916","volume":"19","author":"K-W Kwong","year":"2011","unstructured":"Kwong K-W, Gao L, Gu\u00e9rin R, Zhang Z-L (2011) On the feasibility and efficacy of protection routing in IP networks. IEEE\/ACM Trans Netw 19(5):1543\u20131556","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"2\u20133","key":"3297_CR26","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.tcs.2005.02.007","volume":"339","author":"C-K Lin","year":"2005","unstructured":"Lin C-K, Huang H-M, Hsu L-H (2005) The super connectivity of the pancake graphs and the super laceability of the star graphs. Theor Comput Sci 339(2\u20133):257\u2013271","journal-title":"Theor Comput Sci"},{"issue":"17","key":"3297_CR27","doi-asserted-by":"publisher","first-page":"5474","DOI":"10.1016\/j.disc.2008.12.023","volume":"309","author":"C-K Lin","year":"2009","unstructured":"Lin C-K, Tan JJM, Huang H-M, Hsu DF, Hsu L-H (2009) Mutually independent hamiltonian cycles for the pancake graphs and the star graphs. Discrete Math 309(17):5474\u20135483","journal-title":"Discrete Math"},{"key":"3297_CR28","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.jpdc.2018.08.006","volume":"122","author":"SA Mane","year":"2018","unstructured":"Mane SA, Kandekar SA, Waphare BN (2018) Constructing spanning trees in augmented cubes. J Parallel Distrib Comput 122:188\u2013194","journal-title":"J Parallel Distrib Comput"},{"issue":"3","key":"3297_CR29","doi-asserted-by":"publisher","first-page":"427","DOI":"10.7151\/dmgt.1806","volume":"35","author":"M Matsushita","year":"2015","unstructured":"Matsushita M, Otachi Y, Araki T (2015) Completely independent spanning trees in (partial) $$k$$-trees. Discuss Math Graph Theory 35(3):427\u2013437","journal-title":"Discuss Math Graph Theory"},{"key":"3297_CR30","doi-asserted-by":"crossref","unstructured":"Moinet A, Darties B, Gastineau N, Baril J-L, Togni O (2017) Completely independent spanning trees for enhancing the robustness in ad-hoc Networks. In: Proceedings of 10th IEEE International Workshop on Selected Topics in Mobile and Wireless Computing (STWiWob 2017), Rome, Italy, 9\u201311 Oct, pp 63\u201370","DOI":"10.1109\/WiMOB.2017.8115791"},{"key":"3297_CR31","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2016.08.024","volume":"652","author":"K-J Pai","year":"2016","unstructured":"Pai K-J, Chang J-M (2016) Constructing two completely independent spanning trees in hypercube-variant networks. Theor Comput Sci 652:28\u201337","journal-title":"Theor Comput Sci"},{"key":"3297_CR32","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ipl.2018.09.006","volume":"141","author":"K-J Pai","year":"2019","unstructured":"Pai K-J, Chang J-M (2019) Improving the diameters of completely independent spanning trees in locally twisted cubes. Inf Process Lett 141:22\u201324","journal-title":"Inf Process Lett"},{"issue":"3","key":"3297_CR33","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1109\/TNET.2019.2910019","volume":"27","author":"K-J Pai","year":"2019","unstructured":"Pai K-J, Chang J-M (2019) Dual-CISTs, configuring a protection routing on some Cayley networks. IEEE\/ACM Trans Netw 27(3):1112\u20131123","journal-title":"IEEE\/ACM Trans Netw"},{"key":"3297_CR34","doi-asserted-by":"publisher","first-page":"105874","DOI":"10.1016\/j.ipl.2019.105874","volume":"155","author":"K-J Pai","year":"2020","unstructured":"Pai K-J, Chang R-S, Chang J-M (2020) A well-equalized 3-CIST partition of alternating group graphs. Inf Process Lett 155:105874","journal-title":"Inf Process Lett"},{"key":"3297_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jpdc.2020.02.007","volume":"140","author":"K-J Pai","year":"2020","unstructured":"Pai K-J, Chang R-S, Chang J-M (2020) A protection routing with secure mechanism in M\u00f6bius cubes. J Parallel Distrib Comput 140:1\u201312","journal-title":"J Parallel Distrib Comput"},{"key":"3297_CR36","unstructured":"Pai K-J, Chang R-S, Chang J-M, Performance assessment of protection routings on some Cayley networks. http:\/\/poterp.iem.mcut.edu.tw\/cist2\/"},{"key":"3297_CR37","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2019.03.035","volume":"784","author":"K-J Pai","year":"2019","unstructured":"Pai K-J, Chang R-S, Wu R-Y, Chang J-M (2019) A two-stage tree searching algorithm for finding three completely independent spanning trees. Theor Comput Sci 784:65\u201374","journal-title":"Theor Comput Sci"},{"key":"3297_CR38","unstructured":"Pai K-J, Tang S-M, Chang J-M, Yang J-S (2013) Completely independent spanning trees on complete graphs, complete bipartite graphs and complete tripartite graphs. Adv Intelligent Syst Appl vol 1, Smart Innovation, Systems and Technologies, vol 20. Springer, Berlin, Heidelberg, pp 107\u2013113"},{"issue":"9","key":"3297_CR39","doi-asserted-by":"publisher","first-page":"2514","DOI":"10.1587\/transinf.2014EDL8079","volume":"E97\u2013D","author":"K-J Pai","year":"2014","unstructured":"Pai K-J, Yang J-S, Yao S-C, Tang S-M, Chang J-M (2014) Completely independent spanning trees on some interconnection networks. IEICE Trans Inform Syst E97\u2013D(9):2514\u20132517","journal-title":"IEICE Trans Inform Syst"},{"issue":"4","key":"3297_CR40","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/j.disc.2011.11.015","volume":"312","author":"F P\u00e9terfalvi","year":"2012","unstructured":"P\u00e9terfalvi F (2012) Two counterexamples on completely independent spanning trees. Discrete Math 312(4):808\u2013810","journal-title":"Discrete Math"},{"key":"3297_CR41","first-page":"124546","volume":"362","author":"X-W Qin","year":"2019","unstructured":"Qin X-W, Chang J-M, Hao R-X (2019) Constructing dual-CISTs of DCell data center networks. Appl Math Comput 362:124546","journal-title":"Appl Math Comput"},{"issue":"1","key":"3297_CR42","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1109\/TPDS.2019.2931904","volume":"31","author":"X-W Qin","year":"2020","unstructured":"Qin X-W, Hao R-X, Chang J-M (2020) The existence of completely independent spanning trees for some compound graphs. IEEE Trans Parallel Distrib Syst 31(1):201\u2013210","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"1","key":"3297_CR43","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1006\/jpdc.1994.1066","volume":"22","author":"K Qiu","year":"1994","unstructured":"Qiu K, Akl SG, Meuer H (1994) On some properties and algorithms for the star and pancake interconnection networks. J Parallel Distrib Comput 22(1):16\u201325","journal-title":"J Parallel Distrib Comput"},{"key":"3297_CR44","unstructured":"Satav PR, Jawandhiya PM (2016) Review on single-path multi-path routing protocol in MANET: a study. In: IEEE International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2016), 23\u201325 Dec, Jaipur, India, pp 1\u20136"},{"issue":"3","key":"3297_CR45","first-page":"610","volume":"E86\u2013D","author":"Y Suzuki","year":"2003","unstructured":"Suzuki Y, Kaneko K (2003) An algorithm for node-disjoint paths in pancake graphs. IEICE Trans Inform Syst E86\u2013D(3):610\u2013615","journal-title":"IEICE Trans Inform Syst"},{"issue":"4","key":"3297_CR46","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s11590-012-0455-y","volume":"7","author":"J Tapolcai","year":"2013","unstructured":"Tapolcai J (2013) Sufficient conditions for protection routing in IP networks. Optim Lett 7(4):723\u2013730","journal-title":"Optim Lett"},{"issue":"12","key":"3297_CR47","doi-asserted-by":"publisher","first-page":"2409","DOI":"10.1587\/transinf.2019PAL0001","volume":"E102\u2013D","author":"Y-X Yang","year":"2019","unstructured":"Yang Y-X, Pai K-J, Chang R-S, Chang J-M (2019) Constructing two completely independent spanning trees in balanced hypercubes. IEICE Trans Inform Syst E102\u2013D(12):2409\u20132412","journal-title":"IEICE Trans Inform Syst"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03297-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03297-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03297-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T23:52:46Z","timestamp":1620085966000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03297-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,4]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["3297"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03297-9","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,4]]},"assertion":[{"value":"4 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}