Not being (super)thin or solid is hard: A study of grid Hamiltonicity

DOI10.1016/j.comgeo.2008.11.004zbMath1193.05105OpenAlexW2005353392MaRDI QIDQ924074

David Rappaport, Yurai Núñez-Rodríguez, Sándor P. Fekete, Esther M. Arkin, Valentin Polishchuk, Joseph S. B. Mitchell, Kamrul Islam, Henry Xiao, Henk G. Meijer

Publication date: 27 July 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.11.004

zbMATH Keywords

Hamiltonian cyclegrid graphcovering tourhigh-girth graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Related Items

Unnamed Item, On orthogonally guarding orthogonal polygons with bounded treewidth, The traveling salesman problem on grids with forbidden neighborhoods, Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time, Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs, 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids, Symmetric Connectivity in Wireless Sensor Networks with π/3 Directional Antennas, A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes, On-line exploration of rectangular cellular environments with a rectangular hole, Bounded-angle spanning tree: modeling networks with angular constraints, Walking through waypoints, The complexity of symmetric connectivity in directional wireless sensor networks, Euclidean bottleneck bounded-degree spanning tree ratios, An Improved Strategy for Exploring a Grid Polygon, Many-to-many two-disjoint path covers in cylindrical and toroidal grids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamiltonian properties of triangular grid graphs
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• A polynomial algorithm for b-matchings: An alternative approach
• Advances on the Hamiltonian problem -- a survey
• A lower bound on the number of hamiltonian cycles
• Approximation algorithms for lawn mowing and milling
• Fourier analysis and large independent sets in powers of complete graphs
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• On the Number of Hamiltonian Cycles in Bipartite Graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On two geometric problems related to the travelling salesman problem
• Two New Classes of Hamiltonian Graphs
• The Snowblower Problem
• Finding paths and cycles of superpolylogarithmic length
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Finding a Path of Superlogarithmic Length
• Vertex-unfoldings of simplicial manifolds
• The Traveling Salesman Problem with Distances One and Two
• Hamilton Paths in Grid Graphs
• Optimal Covering Tours with Turn Costs