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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publication2019 IEEE 10th International Conference on Awareness Science and Technology, iCAST 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728138213
DOIs
Publication statusPublished - 2019 Oct
Event10th IEEE International Conference on Awareness Science and Technology, iCAST 2019 - Morioka, Japan
Duration: 2019 Oct 232019 Oct 25

Publication series

Name2019 IEEE 10th International Conference on Awareness Science and Technology, iCAST 2019 - Proceedings

Conference

Conference10th IEEE International Conference on Awareness Science and Technology, iCAST 2019
CountryJapan
CityMorioka
Period19-10-2319-10-25

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Information Systems
  • Artificial Intelligence
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Finding Longest (s, t)-paths of O-shaped Supergrid Graphs in Linear Time'. Together they form a unique fingerprint.

  • Cite this

    Hung, R. W., Keshavarz-Kohjerdi, F., Tseng, Y. M., & Qiu, G. H. (2019). Finding Longest (s, t)-paths of O-shaped Supergrid Graphs in Linear Time. In 2019 IEEE 10th International Conference on Awareness Science and Technology, iCAST 2019 - Proceedings [8923400] (2019 IEEE 10th International Conference on Awareness Science and Technology, iCAST 2019 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICAwST.2019.8923400