logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro