The Longest ( s, t )-Path Problem on O -Shaped Supergrid Graphs

Fatemeh Keshavarz-Kohjerdi and Ruo-Wei Hung ()
Additional contact information
Fatemeh Keshavarz-Kohjerdi: Department of Mathematics and Computer Science, Shahed University, Tehran 3319118651, Iran
Ruo-Wei Hung: Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 413310, Taiwan

Mathematics, 2023, vol. 11, issue 12, 1-26

Abstract: The longest ( s , t ) -path problem on supergrid graphs is known to be NP-complete. However, the complexity of this problem on supergrid graphs with or without holes is still unknown.In the past, we presented linear-time algorithms for solving the longest ( s , t ) -path problem on L -shaped and C -shaped supergrid graphs, which form subclasses of supergrid graphs without holes. In this paper, we will determine the complexity of the longest ( s , t ) -path problem on O -shaped supergrid graphs, which form a subclass of supergrid graphs with holes. These graphs are rectangular supergrid graphs with rectangular holes. It is worth noting that O -shaped supergrid graphs contain L -shaped and C -shaped supergrid graphs as subgraphs, but there is no inclusion relationship between them. We will propose a linear-time algorithm to solve the longest ( s , t ) -path problem on O -shaped supergrid graphs. The longest ( s , t ) -paths of O -shaped supergrid graphs have applications in calculating the minimum trace when printing hollow objects using computer embroidery machines and 3D printers.

Keywords: longest path; Hamiltonian-connected; supergrid graphs; O -shaped supergrid graphs; computerized embroidery machines; 3D printers (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/12/2712/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/12/2712/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:12:p:2712-:d:1171760

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().