The Hamiltonian properties of supergrid graphs

DOI10.1016/J.TCS.2015.08.024MaRDI QIDQ497690zbMATH OpenOpenAlexFDO

Authors Ruo-Wei Hung, Chih-Chia Yao, Shang-Ju Chan

Publication date 25 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.08.024

zbMATH Keywords

grid graphsupergrid graphtriangular grid graphalphabet supergrid graphcomputerized sewing machineHamiltonian propertiesrectangular supergrid graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• Hamiltonian cycles in linear-convex supergrid graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamilton circuit problem on grids

Cites work

• scientific article; zbMATH DE number 3907805 (Why is no real title available?)
• scientific article; zbMATH DE number 3668667 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Algorithmic graph theory and perfect graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Approximating the longest paths in grid graphs
• Bondage number of grid graphs
• Conditional edge-fault Hamiltonicity of augmented cubes
• Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Graph theory
• Hamilton Paths in Grid Graphs
• Hamiltonian Properties of Grid Graphs
• Hamiltonian circuits in interval graph generalizations
• Hamiltonian cycles in T-graphs
• Hamiltonian paths in some classes of grid graphs
• Hamiltonian properties of triangular grid graphs
• Intersections of longest cycles in grid graphs
• On the broadcast independence number of grid graph
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The NP-completeness column: an ongoing guide
• The total bondage number of grid graphs
• Total domination number of grid graphs

Cited in

(11)

• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian connectivity of diagonal grid graphs
• The algorithm and complexity of co-secure domination in geometric intersection graphs
• Hamiltonian (s, t)-paths in solid supergrid graphs
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• The restrained domination and independent restrained domination in extending supergrid graphs
• Restrained domination and its variants in extended supergrid graphs

This page was built for publication: The Hamiltonian properties of supergrid graphs

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