The Hamiltonian properties of supergrid graphs
From MaRDI portal
Publication:497690
DOI10.1016/j.tcs.2015.08.024zbMath1330.05093OpenAlexW2188309853MaRDI QIDQ497690
Ruo-Wei Hung, Shang-Ju Chan, Chih-Chia Yao
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
grid graphsupergrid graphtriangular grid graphalphabet supergrid graphcomputerized sewing machineHamiltonian propertiesrectangular supergrid graph
Related Items (9)
Hamiltonian cycles in linear-convex supergrid graphs ⋮ The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Hamiltonian connectivity of diagonal grid graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
Cites Work
- Hamiltonian paths in some classes of grid graphs
- The total bondage number of grid graphs
- Approximating the longest paths in grid graphs
- A linear-time algorithm for the longest path problem in rectangular grid graphs
- Conditional edge-fault Hamiltonicity of augmented cubes
- Hamiltonian properties of triangular grid graphs
- Hamiltonian circuits in interval graph generalizations
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Hamiltonian cycles in T-graphs
- Total domination number of grid graphs
- An efficient algorithm for constructing Hamiltonian paths in meshes
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Algorithmic graph theory and perfect graphs
- Eulerian disjoint paths problem in grid graphs is NP-complete
- Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
- Bondage number of grid graphs
- On the broadcast independence number of grid graph
- The NP-completeness column: an ongoing guide
- Hamiltonian Properties of Grid Graphs
- Intersections of longest cycles in grid graphs
- Hamilton Paths in Grid Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The Hamiltonian properties of supergrid graphs