Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs

DOI10.1142/s0129054123470019zbMath1529.05100MaRDI QIDQ6066461

S. H. Whitesides, Rahnuma Islam Nishat

Publication date: 16 November 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cyclegrid graphsreconfigurationlocal operations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unnamed Item
• Enumerating Hamiltonian cycles
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• The number of Hamiltonian paths in a rectangular grid
• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids
• Reconfiguring Hamiltonian cycles in L-shaped grid graphs
• Reconfiguration of maximum weight \(b\)-matchings in a graph
• Bend complexity and Hamiltonian cycles in grid graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Complexity of Hamiltonian cycle reconfiguration
• Bemerkungen zum Vierfarbenproblem
• The Hamilton circuit problem on grids
• Hamilton Paths in Grid Graphs
• Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs

This page was built for publication: Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs