← All problems

Traveling Salesman Problem in Solid Grid Graphs

What is the complexity of finding a shortest tour in a solid planar grid graph? A planar grid graph is a graph whose vertices are any set of points on the planar integer lattice and whose edges connect every pair of vertices at unit distance. Distances between nodes correspond to induced shortest-path distances in the graph, which corresponds to \textquotedblleft{}Manhattan\textquotedblright{} distances. A grid graph is solid if it does not have any holes, i.e., its complement in the planar integer lattice is connected.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu