Asset Details
Do you wish to reserve the book?
The Longest (s, t)-Path Problem on O-Shaped Supergrid Graphs
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
The Longest (s, t)-Path Problem on O-Shaped Supergrid Graphs
Do you wish to request the book?
The Longest (s, t)-Path Problem on O-Shaped Supergrid Graphs
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
The Longest (s, t)-Path Problem on O-Shaped Supergrid Graphs
2023
Overview
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.
Publisher
MDPI AG
Subject
