Resumen

El problema de la ruta hamiltoniana para grafos de cuadrícula generales se sabe que es NP-completo. En este artículo, presentamos condiciones necesarias y suficientes para la existencia de rutas hamiltonianas en grafos de cuadrícula de -alfabeto, -alfabeto, -alfabeto y -alfabeto. También presentamos algoritmos de tiempo lineal para encontrar rutas hamiltonianas en estos grafos.

• Materias:Modelado matemático Sistemas estocásticos Productos gráficos Ecuaciones matriciales Métodos de descomposición
• Subjects:Mathematical modeling Stochastic systems Graph products Matrix equations Decomposition methods
• Palabras claves:Camino hamiltoniano; Grafos de rejilla; Np-completo; Alfabeto; Algoritmos de tiempo lineal; Existencia;
• Keywords:Hamiltonian path; Grid graphs; Np-complete; Alphabet; Linear-time algorithms; Existence;