Finding Longest (s, t)-paths of O-shaped Supergrid Graphs in Linear Time

Ruo-Wei Hung | Fatemeh Keshavarz-Kohjerdi | Yuh-Min Tseng | Guo-Hao Qiu

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137171
Date :  2019/12/05
Publish in :     2019 IEEE 10th International Conference on Awareness Science and Technology (iCAST)
DOI :  https://doi.org/10.1109/ICAwST.2019.8923400
Link :  http://dx.doi.org/10.1109/ICAwST.2019.8923400
Keywords :Hamiltonian connectivity, longest (s, t)-path, supergrid graphs, O-shaped supergrid graphs, computerized embroidery machines, 3D printers

Abstract :

---

The longest path and Hamiltonian problems were known to be NP-complete. In spite of many applications of these problems, their complexities are still unknown for many classes of graphs, including supergrid graphs with holes and solid supergrid graphs. In this paper, we will study the complexity of the longest (s, t)-path problem on O-shaped supergrid graphs. The longest (s, t)-path is a simple path from s to t with the largest number of visited vertices. An O-shaped supergrid graph is a rectangular supergrid graph with one rectangular hollow. We will propose a linear-time algorithm to find the longest (s, t)-path of O-shaped supergrid graphs. The longest (s, t)-paths of O-shaped supergrid graphs can be used to compute the smallest stitching path of computerized embroidery machine and 3D printer when a hollow object is printed.

http://dx.doi.org/10.1109/ICAwST.2019.8923400