Strategic oscillation tabu search for improved hierarchical graph drawing

Resumen

En los últimos años, muchas áreas en ciencia, negocios e ingeniería han experimentado un crecimiento enorme en la cantidad de datos que deben analizar. En muchos casos, este análisis depende íntimamente de la visualización de datos y, como resultado, el dibujo de grafos ha emergido como un nuevo campo de investigación. Este artículo aborda el desafío de dibujar grafos jerárquicos, que es uno de los estándares de dibujo más ampliamente utilizados. Introducimos un nuevo modelo matemático para representar automáticamente un grafo basado en la alineación de arcos largos, que combinamos with el objetivo clásico de minimización de cruces de arcos en dibujos jerárquicos. Complementamos nuestra propuesta con un algoritmo heurístico que puede obtener resultados de alta calidad en el tiempo computacional corto requerido por sistemas de dibujo de grafos. Nuestro algoritmo une dos metodologías, búsqueda tabú y oscilación estratégica (SOS), para realizar una exploración rápida y efectiva del espacio de búsqueda. Realizamos experimentación extensa que integra nuestra nueva formulación de programación matemática y la búsqueda tabú SOS dirigida a instancias grandes. Nuestro análisis estadístico confirma la efectividad de esta propuesta.

Citar Esta Publicación

Cavero, S., Pardo, E. G., Glover, F., & Martí, R. (2024). Strategic oscillation tabu search for improved hierarchical graph drawing. Expert Systems with Applications, 243, 122668.