{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T03:18:21Z","timestamp":1790997501894,"version":"4.1.0"},"reference-count":23,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,13]],"date-time":"2022-02-13T00:00:00Z","timestamp":1644710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST 110-2221-E-324-007-MY3"],"award-info":[{"award-number":["MOST 110-2221-E-324-007-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In the past, we proved the Hamiltonian path and cycle problems for general supergrid graphs to be NP-complete. However, they are still open for solid supergrid graphs. In this paper, first we will verify the Hamiltonian cycle property of C-shaped supergrid graphs, which are a special case of solid supergrid graphs. Next, we show that C-shaped supergrid graphs are Hamiltonian connected except in a few conditions. For these excluding conditions of Hamiltonian connectivity, we compute their longest paths. Then, we design a linear-time algorithm to solve the longest path problem in these graphs. The Hamiltonian connectivity of C-shaped supergrid graphs can be applied to compute the optimal stitching trace of computer embroidery machines, and construct the minimum printing trace of 3D printers with a C-like component being printed.<\/jats:p>","DOI":"10.3390\/a15020061","type":"journal-article","created":{"date-parts":[[2022,2,13]],"date-time":"2022-02-13T20:32:30Z","timestamp":1644784350000},"page":"61","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Finding Hamiltonian and Longest (s,t)-Paths of C-Shaped Supergrid Graphs in Linear Time"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7006-2675","authenticated-orcid":false,"given":"Fatemeh","family":"Keshavarz-Kohjerdi","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Shahed University, Tehran 3319118651, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5803-2265","authenticated-orcid":false,"given":"Ruo-Wei","family":"Hung","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 413310, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,13]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Gide to the Theory of NP-Completeness, Freeman."},{"key":"ref_2","unstructured":"Harary, F. (1967). Graph Theory, Addison-Wesley."},{"key":"ref_3","unstructured":"Ascheuer, N. (1996). Hamiltonian Path Problems in the On-Line Optimization of Flexible Manufacturing Systems, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik. Technique Report TR 96-3."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0146-664X(74)80004-3","article-title":"Computing the perceptual boundaries of dot patterns","volume":"3","year":"1974","journal-title":"Comput. Graph. Image Process"},{"key":"ref_5","unstructured":"Beinke, L.W., and Wilson, R.J. (1978). Hamiltonian Graphs, in Selected Topics in Graph Theory, Academic Press."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Preperata, F.P., and Shamos, M.I. (1985). Computational Geometry: An Introduction, Springer.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"ref_7","unstructured":"Toussaint, G.T. (1980, January 1\u20134). Pattern recognition and geometrical complexity. Proceedings of the 5th International Conference on Pattern Recognition, Miami Beach, FL, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0898-1221(88)90213-1","article-title":"A survey of the theory of hypercube graphs","volume":"15","author":"Harary","year":"1988","journal-title":"Comput. Math. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0097-8485(85)80018-8","article-title":"Computer-assisted enumeration ofwalks and self-returning walks on chemical graphs","volume":"9","author":"Balasubramanian","year":"1985","journal-title":"Comput. Chem."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1080\/1536383X.2020.1744573","article-title":"Enumeration of stereo, position andchiral isomers of polysubstituted giant fullerenes: Applications to C180 and C240","volume":"28","author":"Balasubramanian","year":"2020","journal-title":"Fullerenes Nanotub. Carbon Nanostruct."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2021","DOI":"10.1038\/s41467-018-03713-y","article-title":"Hamiltonian path analysis of viral genomes","volume":"9","author":"Twarock","year":"2018","journal-title":"Nat. Commun."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.disopt.2017.06.001","article-title":"The Hamiltonian connectivity of rectangular supergrid graphs","volume":"26","author":"Hung","year":"2017","journal-title":"Discrete Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0020-0190(01)00198-3","article-title":"On computing a longest path in a tree","volume":"81","author":"Bulterman","year":"2002","journal-title":"Inform. Process. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/s00453-010-9411-3","article-title":"The longest path problem has a polynomial solution on interval graphs","volume":"61","author":"Ioannidou","year":"2011","journal-title":"Algorithmica"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1137\/100793529","article-title":"A simple polynomial agorithm for the longest path problem on cocomparability graphs","volume":"26","author":"Mertzios","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.tcs.2015.08.024","article-title":"The Hamiltonian properties of supergrid graphs","volume":"602","author":"Hung","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","first-page":"378","article-title":"The Hamiltonicity, Hamiltonian connectivity, and longest (s,t)-path of L-shaped supergrid graphs","volume":"47","author":"Hung","year":"2020","journal-title":"IAENG Intern. J. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","article-title":"Hamiltonian paths in grid graphs","volume":"11","author":"Itai","year":"1982","journal-title":"SIAM J. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1137\/0405046","article-title":"Hamiltonian properties of grid graphs","volume":"5","author":"Zamfirescu","year":"1992","journal-title":"SIAM J Discrete Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1016\/S0167-8191(02)00135-7","article-title":"An efficient algorithm for constructing Hamiltonian paths in meshes","volume":"28","author":"Chen","year":"2002","journal-title":"Parallel Comput."},{"key":"ref_21","unstructured":"Lenhart, W., and Umans, C. (1997, January 19\u201322). Hamiltonian cycles in solid grid graphs. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS\u201997, Miami Beach, FL, USA."},{"key":"ref_22","unstructured":"Salman, A.N.M. (2005). Contributions to Graph Theory. [Ph.D. Thesis, University of Twente]."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2016.01.024","article-title":"Hamiltonian paths in L-shaped grid graphs","volume":"621","author":"Bagheri","year":"2016","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/61\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:18:40Z","timestamp":1760134720000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,13]]},"references-count":23,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020061"],"URL":"https:\/\/doi.org\/10.3390\/a15020061","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,13]]}}}