Hamilton Paths in Grid Graphs
From MaRDI portal
Publication:4742820
DOI10.1137/0211056zbMath0506.05043OpenAlexW2055336889WikidataQ55894231 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
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, Parliament seating assignment problems, Bounded-angle spanning tree: modeling networks with angular constraints, Open problems around exact algorithms, Flow network design for manufacturing systems layout, The Hamiltonian connectivity of rectangular supergrid graphs, Finding Hamiltonian circuits in quasi-adjoint graphs, Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm, Hamiltonian cycle is polynomial on cocomparability graphs, Matching supply and demand in a sharing economy: classification, computational complexity, and application, The location of median paths on grid graphs, Solitaire clobber played on Cartesian product of graphs, An exact method for scheduling a yard crane, Angle-restricted tours in the plane., Boundary properties of graphs for algorithmic graph problems, Reconstructing polygons from scanner data, Solitaire Clobber on circulant graphs, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Approximating the longest paths in grid graphs, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, Hashiwokakero is NP-complete, Minimizing the number of switch instances on a flexible machine in polynomial time, Honey-pot constrained searching with local sensory information, Complexity of independency and cliquy trees, Hamiltonian properties of triangular grid graphs, A genetic algorithm for the picture maze generation problem, Path-connectivity of lexicographic product graphs, On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies, Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs, A note on the Hamiltonian circuit problem on directed path graphs, A linear time recognition algorithm for proper interval graphs, An approximation algorithm for the longest path problem in solid grid graphs, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, Degree-bounded minimum spanning trees, Euclidean bottleneck bounded-degree spanning tree ratios, The Hamiltonian circuit problem for circle graphs is NP-complete, A linear-time algorithm for the longest path problem in rectangular grid graphs, Positive semidefinite zero forcing numbers of two classes of graphs, Impartial Solitaire Clobber played on Powers of Paths, Strong reducibility of powers of paths and powers of cycles on Impartial Solitaire Clobber, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Approximation algorithms for lawn mowing and milling, Revising Johnson's table for the 21st century, Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs, Reliability problems in multiple path-shaped facility location on networks, Four-point conditions for the TSP: the complete complexity classification, Forests, colorings and acyclic orientations of the square lattice, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, The complexity of quantum circuit mapping with fixed parameters, Finding Hamiltonian circuits in interval graphs, More on the complexity of common superstring and supersequence problems, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs, Competitive on-line coverage of grid environments by a mobile robot, Parameterized complexity of \((A,\ell)\)-path packing
