{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:50:00Z","timestamp":1765889400622,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T00:00:00Z","timestamp":1729296000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T00:00:00Z","timestamp":1729296000000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s10878-024-01207-w","type":"journal-article","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T18:02:42Z","timestamp":1729360962000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The hamiltonian path graph is connected for simple s,\u00a0t paths in rectangular grid graphs"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6987-4855","authenticated-orcid":false,"given":"Rahnuma Islam","family":"Nishat","sequence":"first","affiliation":[]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,19]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Afrati F (1994) The Hamilton circuit problem on grids. RAIRO\u2013Theor Inform Appl\u2013Inform Theorique et Appl 28(6):567\u2013582","key":"1207_CR1","DOI":"10.1051\/ita\/1994280605671"},{"issue":"3","key":"1207_CR2","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/S0097539703434267","volume":"35","author":"EM Arkin","year":"2005","unstructured":"Arkin EM, Bender MA, Demaine ED, Fekete SP, Mitchell JSB, Sethia S (2005) Optimal covering tours with turn costs. SIAM J Comput 35(3):531\u2013566","journal-title":"SIAM J Comput"},{"issue":"6\u20137","key":"1207_CR3","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.comgeo.2008.11.004","volume":"42","author":"EM Arkin","year":"2009","unstructured":"Arkin EM, Fekete SP, Islam K, Meijer H, Mitchell JS, Rodr\u00edguez YN, Polishchuk V, Rappaport D, Xiao H (2009) Not being (super)thin or solid is hard: a study of grid Hamiltonicity. Comput Geom 42(6\u20137):582\u2013605","journal-title":"Comput Geom"},{"issue":"2","key":"1207_CR4","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1111\/cgf.14488","volume":"41","author":"A Bedel","year":"2022","unstructured":"Bedel A, Coudert-Osmont Y, Mart\u00ednez J, Nishat RI, Whitesides S, Lefebvre S (2022) Closed space-filling curves with controlled orientation for 3d printing. Comput Graph Forum 41(2):473\u2013492","journal-title":"Comput Graph Forum"},{"issue":"1","key":"1207_CR5","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/s10878-012-9490-y","volume":"27","author":"M Bonamy","year":"2014","unstructured":"Bonamy M, Johnson M, Lignos I, Patel V, Paulusma D (2014) Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J Comb Optim 27(1):132\u2013143","journal-title":"J Comb Optim"},{"issue":"50","key":"1207_CR6","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma P, Cereceda L (2009) Finding paths between graph colourings: Pspace-completeness and superpolynomial distances. Theor Comput Sci 410(50):5215\u20135226","journal-title":"Theor Comput Sci"},{"issue":"42","key":"1207_CR7","doi-asserted-by":"publisher","first-page":"9159","DOI":"10.1088\/0305-4470\/38\/42\/001","volume":"38","author":"M Bousquet-M\u00e9lou","year":"2005","unstructured":"Bousquet-M\u00e9lou M, Guttmann AJ, Jensen I (2005) Self-avoiding walks crossing a square. J Phys A: Math Gen 38(42):9159","journal-title":"J Phys A: Math Gen"},{"issue":"9","key":"1207_CR8","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1016\/S0167-8191(02)00135-7","volume":"28","author":"SD Chen","year":"2002","unstructured":"Chen SD, Shen H, Topor R (2002) An efficient algorithm for constructing hamiltonian paths in meshes. Parallel Comput 28(9):1293\u20131305","journal-title":"Parallel Comput"},{"issue":"1\u20133","key":"1207_CR9","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(95)00330-Y","volume":"169","author":"KL Collins","year":"1997","unstructured":"Collins KL, Krompart LB (1997) The number of Hamiltonian paths in a rectangular grid. Discret Math 169(1\u20133):29\u201338","journal-title":"Discret Math"},{"unstructured":"Combinatorial reconfiguration. Report from the banff workshop on combinatorial reconfiguration in 2017. https:\/\/www.birs.ca\/events\/2022\/5-day-workshops\/22w5090","key":"1207_CR10"},{"unstructured":"Combinatorial reconfiguration wiki. (2024). https:\/\/reconf.wikidot.com\/","key":"1207_CR11"},{"issue":"7","key":"1207_CR12","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1088\/0305-4470\/26\/7\/012","volume":"26","author":"AR Conway","year":"1993","unstructured":"Conway AR, Enting IG, Guttmann AJ (1993) Algebraic techniques for enumerating self-avoiding walks on the square lattice. J Phys A: Math Gen 26(7):1519","journal-title":"J Phys A: Math Gen"},{"unstructured":"Everett H (1986) Hamiltonian paths in nonrectangular grid graphs. Master\u2019s thesis, University of Saskatchewan, Canada","key":"1207_CR13"},{"doi-asserted-by":"crossref","unstructured":"Fellows M, Giannopoulos P, Knauer C, Paul C, Rosamond FA, Whitesides S, Yu N (2010) Milling a graph with turn costs: a parameterized complexity perspective. In: WG 2010, LNCS, vol. 6410, pp. 123\u2013134","key":"1207_CR14","DOI":"10.1007\/978-3-642-16926-7_13"},{"unstructured":"G\u00f6bel F (1979) On the number of hamilton cycles in product graphs. Technische Hogeschool Twente","key":"1207_CR15"},{"issue":"6","key":"1207_CR16","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan P, Kolaitis PG, Maneva E, Papadimitriou CH (2009) The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM J Comput 38(6):2330\u20132355","journal-title":"SIAM J Comput"},{"doi-asserted-by":"crossref","unstructured":"Gorbenko A, Popov V, Sheka A (2012) Localization on discrete grid graphs. In: CICA 2011, pp. 971\u2013978. Springer Netherlands, Dordrecht","key":"1207_CR17","DOI":"10.1007\/978-94-007-1839-5_105"},{"issue":"24","key":"1207_CR18","doi-asserted-by":"publisher","first-page":"6166","DOI":"10.1016\/j.disc.2007.11.040","volume":"308","author":"VS Gordon","year":"2008","unstructured":"Gordon VS, Orlovich YL, Werner F (2008) Hamiltonian properties of triangular grid graphs. Discret Math 308(24):6166\u20136188","journal-title":"Discret Math"},{"unstructured":"Islam K, Meijer H, Rodr\u00edguez YN, Rappaport D, Xiao H (2007) Hamilton circuits in hexagonal grid graphs. In: CCCG 2007, pp. 85\u201388","key":"1207_CR19"},{"issue":"4","key":"1207_CR20","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai A, Papadimitriou CH, Szwarcfiter JL (1982) Hamilton paths in grid graphs. SIAM J Comput 11(4):676\u2013686","journal-title":"SIAM J Comput"},{"issue":"12","key":"1207_CR21","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito T, Demaine ED, Harvey NJ, Papadimitriou CH, Sideri M, Uehara R, Uno Y (2011) On the complexity of reconfiguration problems. Theor Comput Sci 412(12):1054\u20131065","journal-title":"Theor Comput Sci"},{"issue":"12","key":"1207_CR22","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito T, Demaine ED, Harvey NJ, Papadimitriou CH, Sideri M, Uehara R, Uno Y (2011) On the complexity of reconfiguration problems. Theor Comput Sci 412(12):1054\u20131065","journal-title":"Theor Comput Sci"},{"unstructured":"Iwashita H, Nakazawa Y, Kawahara J, Uno T, ichi Minato S (2013) Efficient computation of the number of paths in a grid graph with minimal perfect hash functions. Tech. Rep. TCS-TR-A-13-64, Division of Computer Science, Hokkaido University","key":"1207_CR23"},{"key":"1207_CR24","doi-asserted-by":"publisher","first-page":"14667","DOI":"10.1088\/1751-8113\/40\/49\/003","volume":"40","author":"JL Jacobsen","year":"2007","unstructured":"Jacobsen JL (2007) Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions. J Phys A: Math Theor 40:14667\u201314678","journal-title":"J Phys A: Math Theor"},{"key":"1207_CR25","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2016.01.024","volume":"621","author":"F Keshavarz-Kohjerdi","year":"2016","unstructured":"Keshavarz-Kohjerdi F, Bagheri A (2016) Hamiltonian paths in L-shaped grid graphs. Theor Comput Sci 621:37\u201356","journal-title":"Theor Comput Sci"},{"key":"1207_CR26","volume":"436","author":"F Keshavarz-Kohjerdi","year":"2023","unstructured":"Keshavarz-Kohjerdi F, Bagheri A (2023) Finding hamiltonian cycles of truncated rectangular grid graphs in linear time. Appl Math Comput 436:127513","journal-title":"Appl Math Comput"},{"issue":"2","key":"1207_CR27","doi-asserted-by":"publisher","first-page":"61","DOI":"10.3390\/a15020061","volume":"15","author":"F Keshavarz-Kohjerdi","year":"2022","unstructured":"Keshavarz-Kohjerdi F, Hung R (2022) Finding hamiltonian and longest (s, t)-paths of c-shaped supergrid graphs in linear time. Algorithms 15(2):61","journal-title":"Algorithms"},{"unstructured":"Knuth DE (2009) The Art of Computer Programming, Volume 4, Fascicle 1. Addison-Wesley Professional, Boston, MA, USA","key":"1207_CR28"},{"issue":"3","key":"1207_CR29","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1006\/eujc.1994.1031","volume":"15","author":"YHH Kwong","year":"1994","unstructured":"Kwong YHH, Rogers DG (1994) A matrix method for counting hamiltonian cycles on grid graphs. Eur J Comb 15(3):277\u2013283","journal-title":"Eur J Comb"},{"unstructured":"Lignos I (2017) Reconfigurations of combinatorial problems: graph colouring and Hamiltonian cycle. Ph.D. thesis, Durham University","key":"1207_CR30"},{"issue":"1","key":"1207_CR31","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2017","unstructured":"Mouawad AE, Nishimura N, Raman V, Simjour N, Suzuki A (2017) On the parameterized complexity of reconfiguration problems. Algorithmica 78(1):274\u2013297","journal-title":"Algorithmica"},{"issue":"6","key":"1207_CR32","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1108\/RPJ-01-2013-0011","volume":"20","author":"P Muller","year":"2014","unstructured":"Muller P, Hascoet JY, Mognol P (2014) Toolpaths for additive manufacturing of functionally graded materials (FGM) parts. Rapid Prototyp J 20(6):511\u2013522","journal-title":"Rapid Prototyp J"},{"issue":"4","key":"1207_CR33","doi-asserted-by":"publisher","first-page":"281","DOI":"10.7155\/jgaa.00624","volume":"27","author":"R Nishat","year":"2023","unstructured":"Nishat R, Srinivasan V, Whitesides S (2023) 1-complex $$s, t$$ hamiltonian paths: structure and reconfiguration in rectangular grids. J Graph Algorithms Appl 27(4):281\u2013327. https:\/\/doi.org\/10.7155\/jgaa.00624","journal-title":"J Graph Algorithms Appl"},{"unstructured":"Nishat RI (2020) Reconfiguration of Hamiltonian cycles and paths in grid graphs. Ph.D. thesis, University of Victoria, Canada","key":"1207_CR34"},{"doi-asserted-by":"crossref","unstructured":"Nishat RI, Srinivasan V, Whitesides S (2021) Reconfiguring simple s,t Hamiltonian paths in rectangular grid graphs. In: IWOCA 2021, LNCS, vol. 12757, pp. 501\u2013515","key":"1207_CR35","DOI":"10.1007\/978-3-030-79987-8_35"},{"doi-asserted-by":"crossref","unstructured":"Nishat RI, Srinivasan V, Whitesides S (2022) 1-complex $$s,t$$ hamiltonian paths: structure and reconfiguration in rectangular grids. In: WALCOM 2022, LNCS, vol. 13174, pp. 59\u201370","key":"1207_CR36","DOI":"10.1007\/978-3-030-96731-4_6"},{"doi-asserted-by":"crossref","unstructured":"Nishat RI, Srinivasan V, Whitesides S (2022) The hamiltonian path graph is connected for simple s, t paths in rectangular grid graphs. In: COCOON\u201922, LNCS, vol. 13595, pp. 463\u2013475","key":"1207_CR37","DOI":"10.1007\/978-3-031-22105-7_41"},{"doi-asserted-by":"crossref","unstructured":"Nishat RI, Whitesides S (2017) Bend complexity and Hamiltonian cycles in grid graphs. In: COCOON 2017, LNCS, vol. 10392, pp. 445\u2013456","key":"1207_CR38","DOI":"10.1007\/978-3-319-62389-4_37"},{"doi-asserted-by":"crossref","unstructured":"Nishat RI, Whitesides S (2019) Reconfiguring Hamiltonian cycles in l-shaped grid graphs. In: WG 2019, LNCS, vol. 11789, pp. 325\u2013337","key":"1207_CR39","DOI":"10.1007\/978-3-030-30786-8_25"},{"issue":"4","key":"1207_CR40","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"N Nishimura","year":"2018","unstructured":"Nishimura N (2018) Introduction to reconfiguration. Algorithms 11(4):52","journal-title":"Algorithms"},{"issue":"4","key":"1207_CR41","doi-asserted-by":"publisher","first-page":"4.7","DOI":"10.37236\/4510","volume":"21","author":"V Pettersson","year":"2014","unstructured":"Pettersson V (2014) Enumerating Hamiltonian cycles. Electron J Comb 21(4):4.7","journal-title":"Electron J Comb"},{"issue":"2\u20133","key":"1207_CR42","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s004540010051","volume":"24","author":"JR Reay","year":"2000","unstructured":"Reay JR, Zamfirescu T (2000) Hamiltonian cycles in t-graphs. Discrete Comput Geom 24(2\u20133):497\u2013502","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"1207_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.37236\/1694","volume":"10","author":"F Ruskey","year":"2003","unstructured":"Ruskey F, Sawada J (2003) Bent hamilton cycles in $$ d $$-dimensional grid graphs. Electron J Comb 10(1):1\u201318","journal-title":"Electron J Comb"},{"key":"1207_CR44","first-page":"109","volume":"21","author":"R Stoyan","year":"1996","unstructured":"Stoyan R, Strehl V (1996) Enumeration of hamiltonian circuits in rectangular grids. J Comb Math Comb Comput 21:109\u2013128","journal-title":"J Comb Math Comb Comput"},{"issue":"9","key":"1207_CR45","doi-asserted-by":"publisher","first-page":"140","DOI":"10.3390\/a11090140","volume":"11","author":"A Takaoka","year":"2018","unstructured":"Takaoka A (2018) Complexity of Hamiltonian cycle reconfiguration. Algorithms 11(9):140","journal-title":"Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Umans C, Lenhart W (1997) Hamiltonian cycles in solid grid graphs. In: FOCS\u201997, pp. 496\u2013505","key":"1207_CR46","DOI":"10.1109\/SFCS.1997.646138"},{"issue":"4","key":"1207_CR47","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1020853410145","volume":"6","author":"S Winter","year":"2002","unstructured":"Winter S (2002) Modeling costs of turns in route planning. GeoInformatica 6(4):345\u2013361","journal-title":"GeoInformatica"},{"issue":"4","key":"1207_CR48","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1137\/0405046","volume":"5","author":"C Zamfirescu","year":"1992","unstructured":"Zamfirescu C, Zamfirescu T (1992) Hamiltonian properties of grid graphs. SIAM J Discrete Math 5(4):564\u2013570","journal-title":"SIAM J Discrete Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01207-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01207-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01207-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T11:04:54Z","timestamp":1730977494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01207-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,19]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1207"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01207-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,10,19]]},"assertion":[{"value":"6 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"31"}}