{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T03:10:22Z","timestamp":1741403422176,"version":"3.38.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Innovations Syst Softw Eng"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s11334-022-00494-y","type":"journal-article","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T09:03:21Z","timestamp":1667898201000},"page":"121-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Spanning cactus existence in generalized Petersen graphs"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7388-0211","authenticated-orcid":false,"given":"Krishna","family":"Daripa","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,8]]},"reference":[{"key":"494_CR1","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications"},{"issue":"3","key":"494_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0095-8956(83)90042-4","volume":"34","author":"B Alspach","year":"1983","unstructured":"Alspach B (1983) The classification of Hamiltonian generalized Petersen graphs. J Comb Theory, Series B 34(3):293\u2013312","journal-title":"J Comb Theory, Series B"},{"issue":"2","key":"494_CR3","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0095-8956(81)80026-3","volume":"31","author":"B Alspach","year":"1981","unstructured":"Alspach B, Robinson PJ, Rosenfeld M (1981) A result on Hamiltonian cycles in generalized Petersen graphs. J Comb Theory, Series B 31(2):225\u2013231","journal-title":"J Comb Theory, Series B"},{"issue":"3","key":"494_CR4","doi-asserted-by":"publisher","first-page":"475","DOI":"10.4134\/JKMS.2012.49.3.475","volume":"49","author":"A Zitnik","year":"2012","unstructured":"Zitnik A, Horvat B, Pisanski T (2012) All generalized Petersen graphs are unit-distance graphs. J Korean Math Soc 49(3):475\u201391","journal-title":"J Korean Math Soc"},{"issue":"7833","key":"494_CR5","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1038\/s41586-020-2871-y","volume":"587","author":"J Armstrong","year":"2020","unstructured":"Armstrong J, Hickey G, Diekhans M, Fiddes IT, Novak AM, Deran A, Fang Q, Xie D, Feng S, Stiller J, Genereux D, Johnson J, Marinescu VD, Alf\u00f6ldi J, Harris RS, Lindblad-Toh K, Haussler D, Karlsson E, Jarvis ED, Zhang G, Paten B (2020) Progressive cactus is a multiple-genome aligner for the thousand-genome era. Nature 587(7833):246\u2013251","journal-title":"Nature"},{"issue":"2","key":"494_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0095-8956(78)90019-9","volume":"24","author":"K Bannai","year":"1978","unstructured":"Bannai K (1978) Hamiltonian cycles in generalized Petersen graphs. J Comb Theory, Series B 24(2):181\u2013188","journal-title":"J Comb Theory, Series B"},{"issue":"2","key":"494_CR7","doi-asserted-by":"publisher","first-page":"199","DOI":"10.7155\/jgaa.00255","volume":"16","author":"B Ben-Moshe","year":"2012","unstructured":"Ben-Moshe B, Dvir A, Segal M, Tamir A (2012) Centdian computation in cactus graphs. J Graph Algorithms Appl 16(2):199\u2013224","journal-title":"J Graph Algorithms Appl"},{"issue":"1","key":"494_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.4153\/CMB-1972-012-3","volume":"15","author":"JA Bondy","year":"1972","unstructured":"Bondy JA (1972) Variations on the Hamiltonian theme. Can Math Bull 15(1):57\u201362","journal-title":"Can Math Bull"},{"issue":"1","key":"494_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2140\/pjm.1972.40.53","volume":"40","author":"F Castagna","year":"1972","unstructured":"Castagna F, Prins G (1972) Every generalized Petersen graph has a tait coloring. Pac J Math 40(1):53\u201358","journal-title":"Pac J Math"},{"issue":"1","key":"494_CR10","first-page":"121","volume":"10","author":"K Das","year":"2008","unstructured":"Das K, Pal M (2008) An optimal algorithm to find maximum and minimum height spanning trees on cactus graphs. Adv Model Optim 10(1):121\u2013134","journal-title":"Adv Model Optim"},{"issue":"11","key":"494_CR11","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1016\/j.ipl.2015.06.009","volume":"115","author":"Alak Kumar Datta","year":"2015","unstructured":"Alak Kumar Datta (2015) Approximate spanning cactus. Inf Process Lett 115(11):828\u2013832","journal-title":"Inf Process Lett"},{"key":"494_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.dam.2017.08.020","volume":"233","author":"Alak Kumar Datta and Chinmay Debnath","year":"2017","unstructured":"Alak Kumar Datta and Chinmay Debnath (2017) Spanning cactus: complexity and extensions. Discret Appl Math 233:19\u201328","journal-title":"Discret Appl Math"},{"key":"494_CR13","doi-asserted-by":"crossref","unstructured":"Debnath C, Datta AK (2020) A short note on spanning cactus problem of Petersen graph. In: Subhojit D, Valentina\u00a0EB, Anna E, and Sadhan G, (Eds.), intelligent techniques and applications in science and technology, Cham, Springer International Publishing, pp. 757\u2013760","DOI":"10.1007\/978-3-030-42363-6_88"},{"key":"494_CR14","doi-asserted-by":"crossref","unstructured":"Debnath C, Datta A (2020) Spanning cactus existence in a three-dimensional (3 x 3 x 3) grid. In: Proceedings of the international conference on innovative computing & communications (ICICC)","DOI":"10.2139\/ssrn.3566785"},{"key":"494_CR15","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractibility: a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco"},{"issue":"4","key":"494_CR16","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Tarjan RE (1976) The planar Hamiltonian circuit problem is np-complete. SIAM J Comput 5(4):704\u2013714","journal-title":"SIAM J Comput"},{"issue":"4","key":"494_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2635825","volume":"6","author":"A G\u00f6bel","year":"2014","unstructured":"G\u00f6bel A, Goldberg LA, Richerby D (2014) The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans Comput Theory (TOCT) 6(4):1\u201329","journal-title":"ACM Trans Comput Theory (TOCT)"},{"key":"494_CR18","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic MC (1980) Algorithmic graph theory and perfect graphs. Academic Press, New York"},{"issue":"1","key":"494_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.dam.2012.08.006","volume":"161","author":"SN Kabadi","year":"2013","unstructured":"Kabadi SN, Punnen AP (2013) Spanning cactus of a graph: existence, extension, optimization and approximation. Discret Appl Math 161(1):167\u2013175","journal-title":"Discret Appl Math"},{"issue":"1","key":"494_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-15-99","volume":"15","author":"B Kehr","year":"2014","unstructured":"Kehr B, Trappe K, Holtgrewe M, Reinert K (2014) Genome alignment with graph data structures: a comparison. BMC Bioinformatics 15(1):1\u201320","journal-title":"BMC Bioinformatics"},{"key":"494_CR21","unstructured":"Krnc Matja\u017e, Pisanski T (2018) Characterization of generalized Petersen graphs that are Kronecker covers. arXiv preprint arXiv:1802.07134,"},{"issue":"5","key":"494_CR22","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1089\/cmb.2014.0146","volume":"22","author":"N Nguyen","year":"2015","unstructured":"Nguyen N, Hickey G, Zerbino DR, Raney B, Earl D, Armstrong J, Kent WJ, Haussler D, Paten B (2015) Building a pan-genome reference for a population. J Comput Biol 22(5):387\u2013401","journal-title":"J Comput Biol"},{"issue":"1","key":"494_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.dam.2004.08.006","volume":"146","author":"A Palbom","year":"2005","unstructured":"Palbom A (2005) Complexity of the directed spanning cactus problem. Discret Appl Math 146(1):81\u201391","journal-title":"Discret Appl Math"},{"issue":"3","key":"494_CR24","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1089\/cmb.2010.0252","volume":"18","author":"B Paten","year":"2011","unstructured":"Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B, Haussler D (2011) Cactus graphs for genome comparisons. J Comput Biol 18(3):469\u2013481","journal-title":"J Comput Biol"},{"key":"494_CR25","doi-asserted-by":"crossref","unstructured":"Paten B, Diekhans M, Earl D, St John J, Ma J, Suh B, Haussler D (2010) Cactus graphs for genome comparisons. In: Annual international conference on research in computational molecular biology, Springer, pp. 410\u2013425","DOI":"10.1007\/978-3-642-12683-3_27"},{"issue":"9","key":"494_CR26","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1101\/gr.123356.111","volume":"21","author":"B Paten","year":"2011","unstructured":"Paten B, Earl D, Nguyen N, Diekhans M, Zerbino D, Haussler D (2011) Cactus: Algorithms for genome multiple sequence alignment. Genome Res 21(9):1512\u20131528","journal-title":"Genome Res"},{"issue":"7","key":"494_CR27","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1089\/cmb.2017.0251","volume":"25","author":"B Paten","year":"2018","unstructured":"Paten B, Eizenga JM, Rosen YM, Novak AM, Garrison E, Hickey G (2018) Superbubbles, ultrabubbles, and cacti. J Comput Biol 25(7):649\u2013663","journal-title":"J Comput Biol"},{"key":"494_CR28","unstructured":"Robertson N (1969) Graphs minimal under girth, valency and connectivity constraints. PhD thesis, University of Waterloo"},{"issue":"1","key":"494_CR29","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0095-8956(89)90064-6","volume":"47","author":"AJ Schwenk","year":"1989","unstructured":"Schwenk AJ (1989) Enumeration of Hamiltonian cycles in certain generalized Petersen graphs. J Comb Theory, Series B 47(1):53\u201359","journal-title":"J Comb Theory, Series B"},{"key":"494_CR30","doi-asserted-by":"crossref","unstructured":"Shuguang L, Xiao X (2010) Correlation k-clustering with pre-clustered items on cactus graphs. In: 2010 5th international conference on computer science education, pp. 1846\u20131848","DOI":"10.1109\/ICCSE.2010.5593807"},{"issue":"1","key":"494_CR31","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1038\/s41592-020-01045-8","volume":"18","author":"L Tang","year":"2021","unstructured":"Tang L (2021) Scaling up multiple-genome alignments. Nat Methods 18(1):33","journal-title":"Nat Methods"},{"issue":"2","key":"494_CR32","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/S0021-9800(69)80116-X","volume":"6","author":"ME Watkins","year":"1969","unstructured":"Watkins ME (1969) A theorem on Tait colorings with an application to the generalized Petersen graphs. J Comb Theory 6(2):152\u2013164","journal-title":"J Comb Theory"}],"container-title":["Innovations in Systems and Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11334-022-00494-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11334-022-00494-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11334-022-00494-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T02:41:25Z","timestamp":1741401685000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11334-022-00494-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,8]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["494"],"URL":"https:\/\/doi.org\/10.1007\/s11334-022-00494-y","relation":{},"ISSN":["1614-5046","1614-5054"],"issn-type":[{"type":"print","value":"1614-5046"},{"type":"electronic","value":"1614-5054"}],"subject":[],"published":{"date-parts":[[2022,11,8]]},"assertion":[{"value":"26 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}