The Hamiltonian connectivity of rectangular supergrid graphs

DOI10.1016/j.disopt.2017.06.001zbMath1387.05140OpenAlexW2725940624MaRDI QIDQ1751246

Ruo-Wei Hung, Chin-Feng Li, Jong-Shin Chen, Qing-Song Su

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2017.06.001

zbMATH Keywords

longest pathgrid graphcomputer sewing machineHamiltonian connectivityrectangular supergrid graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ Restrained domination and its variants in extended 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid graphs
• The longest path problem has a polynomial solution on interval graphs
• Fault-tolerant Hamiltonicity of twisted cubes
• Approximating the longest paths in grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• The pancyclicity and the Hamiltonian-connectivity of the generalized base-\(b\) hypercube
• Hamiltonian properties of triangular grid graphs
• Hamiltonian connectivity of the WK-recursive network with faulty nodes
• Hamiltonian circuits in interval graph generalizations
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• On some super fault-tolerant Hamiltonian graphs
• Hamiltonian cycles in T-graphs
• On computing a longest path in a tree
• 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
• Hamiltonian properties on the class of hypercube-like networks
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes
• An approximation algorithm for the longest path problem in solid grid graphs
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• The NP-completeness column: an ongoing guide
• Hamiltonian Properties of Grid Graphs
• Hamilton Paths in Grid Graphs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
• Hypercomplete: A pancyclic recursive topology for large-scale distributed multicomputer systems
• A new class of interconnection networks based on the alternating group
• Hamiltonian paths in \(L\)-shaped grid graphs

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