Encontrando caminos hamiltonianos y más largos de grafos supercuadrícula en forma de S en tiempo lineal
Autores: Keshavarz-Kohjerdi, Fatemeh; Hung, Ruo-Wei
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Encontrando caminos hamiltonianos y más largos de grafos supercuadrícula en forma de S en tiempo lineal
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Hamiltoniano
Superred
Grafos
Conectados
Camino
Ciclo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 40
Citaciones: Sin citaciones
Un grafo se llama conexo hamiltoniano si contiene un camino hamiltoniano entre dos vértices distintos. En el pasado, demostramos que los problemas de camino y ciclo hamiltoniano para grafos supergrid generales son NP-completos. Sin embargo, aún están abiertos para grafos supergrid sólidos. En este documento, primero verificaremos la propiedad de ciclo hamiltoniano de los grafos supergrid en forma de - , que son un caso especial de grafos supergrid sólidos. A continuación, mostramos que los grafos supergrid en forma de - son conexos hamiltonianos excepto en algunas condiciones. Para estas condiciones de exclusión de conectividad hamiltoniana, calculamos sus caminos más largos. Luego, diseñamos un algoritmo de tiempo lineal para resolver el problema del camino más largo en estos grafos. La conectividad hamiltoniana de los grafos supergrid en forma de - se puede aplicar para calcular el trazado de costura óptimo de máquinas de bordado computarizadas, y construir el trazado de impresión mínimo de impresoras 3D con un componente en forma de - siendo impreso.
Descripción
Un grafo se llama conexo hamiltoniano si contiene un camino hamiltoniano entre dos vértices distintos. En el pasado, demostramos que los problemas de camino y ciclo hamiltoniano para grafos supergrid generales son NP-completos. Sin embargo, aún están abiertos para grafos supergrid sólidos. En este documento, primero verificaremos la propiedad de ciclo hamiltoniano de los grafos supergrid en forma de - , que son un caso especial de grafos supergrid sólidos. A continuación, mostramos que los grafos supergrid en forma de - son conexos hamiltonianos excepto en algunas condiciones. Para estas condiciones de exclusión de conectividad hamiltoniana, calculamos sus caminos más largos. Luego, diseñamos un algoritmo de tiempo lineal para resolver el problema del camino más largo en estos grafos. La conectividad hamiltoniana de los grafos supergrid en forma de - se puede aplicar para calcular el trazado de costura óptimo de máquinas de bordado computarizadas, y construir el trazado de impresión mínimo de impresoras 3D con un componente en forma de - siendo impreso.