Hamiltonian (s, t)-paths in solid supergrid graphs

DOI10.1007/S40314-024-02614-9MaRDI QIDQ6495481zbMATH OpenFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 30 April 2024

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S40314-024-02614-9

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Recommendations

• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs
• The Hamiltonian properties of supergrid graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7696614 (Why is no real title available?)
• A condition on Hamilton-connected line graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• An approximation algorithm for the longest cycle problem in solid grid graphs
• An approximation algorithm for the longest path problem in solid grid graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Computing and Combinatorics
• Graph theory with applications
• Hamilton Paths in Grid Graphs
• Hamiltonian cycles in T-graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in L-shaped grid graphs
• Hamiltonian properties of triangular grid graphs
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Off-line exploration of rectangular cellular environments with a rectangular obstacle
• Reconfiguring Hamiltonian cycles in L-shaped grid graphs
• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• Survey on path and cycle embedding in some networks
• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamiltonian properties of supergrid graphs
• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs

Cited in

(3)

• Sufficient conditions for Hamiltonian properties of graphs based on the difference of Zagreb indices
• The Hamiltonian (s, t)-path problem in odd-sized H-alphabet grid graphs
• Hamiltonicity of rectangular grid graphs (meshes) with an L-shaped hole

This page was built for publication: Hamiltonian (s, t)-paths in solid supergrid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6495481)