Not being (super)thin or solid is hard: A study of grid Hamiltonicity
type: Item
instance of: scholarly article
title: Not being (super)thin or solid is hard: A study of grid Hamiltonicity
zbMATH Open document ID: 1193.05105
author: Esther M. Arkin
author: Sándor P. Fekete
author: Kamrul Islam
author: Joseph S. B. Mitchell
author: Yurai Núñez-Rodríguez
author: Valentin Polishchuk
author: David Rappaport
author: Henry Xiao
author: Henk Meijer
published in: Computational Geometry
publication date: 2009-07-27T00:00:00Z
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5587032
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: grid graph
zbMATH Keywords: high-girth graph
zbMATH Keywords: covering tour
MaRDI profile type: Publication
full work available at URL: j.comgeo.2008.11.004
OpenAlex ID: W2005353392
cites work: A polynomial algorithm for b-matchings: An alternative approach
cites work: Optimal Covering Tours with Turn Costs
cites work: The Snowblower Problem
cites work: Approximation algorithms for lawn mowing and milling
cites work: Two New Classes of Hamiltonian Graphs
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: Finding a Path of Superlogarithmic Length
cites work: Q4536693
cites work: Vertex-unfoldings of simplicial manifolds
cites work: Q3772257
cites work: Finding large cycles in Hamiltonian graphs
cites work: Finding paths and cycles of superpolylogarithmic length
cites work: An improved upper bound for the TSP in cubic 3-edge-connected graphs
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Fourier analysis and large independent sets in powers of complete graphs
cites work: Hamiltonian properties of triangular grid graphs
cites work: Advances on the Hamiltonian problem -- a survey
cites work: A lower bound on the number of hamiltonian cycles
cites work: Hamilton Paths in Grid Graphs
cites work: Q3701213
cites work: Q4142699
cites work: Q3576725
cites work: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
cites work: Q3621130
cites work: On two geometric problems related to the travelling salesman problem
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: Rectilinear planar layouts and bipolar orientations of planar graphs
cites work: A unified approach to visibility representations of planar graphs
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
cites work: On the number of Hamiltonian cycles in bipartite graphs
DOI: 10.1016/J.COMGEO.2008.11.004
description: scientific article; zbMATH DE number 5587032