Hamilton Paths in Grid Graphs
From MaRDI portal
Publication:4742820
DOI10.1137/0211056zbMath0506.05043DBLPjournals/siamcomp/ItaiPS82OpenAlexW2055336889WikidataQ55894231 ScholiaQ55894231MaRDI QIDQ4742820
Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211056
NP-completenessHamiltonian pathNP-complete problemEuclidean traveling salesman problemrectangular grid graphs
Related Items (only showing first 100 items - show all)
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs ⋮ Signless normalized Laplacian for hypergraphs ⋮ How to Sort by Walking on a Tree ⋮ Unnamed Item ⋮ Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ Unnamed Item ⋮ The Computational Complexity of Portal and Other 3D Video Games ⋮ On embeddability of unit disk graphs onto straight lines ⋮ On the computational difficulty of the terminal connection problem ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Gamma deployment problem in grids: hardness and new integer linear programming formulation ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ Two New Classes of Hamiltonian Graphs ⋮ Lower Bounds for Maximum Weighted Cut ⋮ The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids ⋮ The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs ⋮ Unit-length rectangular drawings of graphs ⋮ Edge deletion to tree-like graph classes ⋮ Dead ends on wreath products and lamplighter groups ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Sequentially swapping tokens: further on graph classes ⋮ A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes ⋮ On length-sensitive Fréchet similarity ⋮ Methods for determining cycles of a specific length in undirected graphs with edge weights ⋮ On-line exploration of rectangular cellular environments with a rectangular hole ⋮ The complexity landscape of disaster‐aware network extension problems ⋮ Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching ⋮ Minor embedding in broken chimera and derived graphs is NP-complete ⋮ The bisection width of grid graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The snowblower problem ⋮ A New Lower Bound for Positive Zero Forcing ⋮ The Hamilton circuit problem on grids ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS ⋮ Vertex-edge domination in unit disk graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Bipartite graphs of small readability ⋮ Hamiltonian paths in \(L\)-shaped grid graphs ⋮ On Covering Points with Minimum Turns ⋮ On efficient connectivity-preserving transformations in a grid ⋮ Minimizing total interference in asymmetric sensor networks ⋮ Distributed transformations of Hamiltonian shapes based on line moves ⋮ Distributed transformations of Hamiltonian shapes based on line moves ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ New results about impartial solitaire clobber ⋮ An Improved Strategy for Exploring a Grid Polygon ⋮ SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS ⋮ Solving the Watchman Route Problem with Heuristic Search ⋮ Solving the Rubik's Cube Optimally is NP-complete ⋮ An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ On the terminal connection problem ⋮ Computing the zig-zag number of directed graphs ⋮ A mobility model for studying wireless communication and the complexity of problems in the model ⋮ Solitaire clobber ⋮ The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree ⋮ Hamiltonian circuits in interval graph generalizations ⋮ Bipartite permutation graphs ⋮ Euclidean movement minimization ⋮ Kernelization of edge perfect code and its variants ⋮ Heuristics and bounds for the travelling salesman location problem on the plane ⋮ The number of Hamiltonian paths in a rectangular grid ⋮ 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ Fault-tolerant Hamiltonicity in a class of faulty meshes ⋮ A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole ⋮ Extensive facility location problems on networks: an updated review ⋮ Mim-width. I. Induced path problems ⋮ How to sort by walking and swapping on paths and trees ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ Extended formulation for hop constrained distribution network configuration problems ⋮ Bounded-degree minimum-radius spanning trees in wireless sensor networks ⋮ Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time ⋮ Grid exploration by a swarm of autonomous robots with minimum repetitions ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ Token shifting on graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Liar's domination in unit disk graphs ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ Hamiltonian paths in some classes of grid graphs ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ Minimum covering with travel cost ⋮ Permutation reconstruction from differences ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Unit disk graphs ⋮ Splitting (complicated) surfaces is hard ⋮ On the structure and complexity of the 2-connected Steiner network problem in the plane ⋮ Constructing edge-disjoint Steiner paths in lexicographic product networks ⋮ The Hamiltonian properties of supergrid graphs ⋮ Watchman routes under limited visibility ⋮ NP-hard graph problems and boundary classes of graphs
This page was built for publication: Hamilton Paths in Grid Graphs
