Algoritmos para el problema del clic máximo con paralelismo de bits

Vol 56, 2024 - 309849
Trabalho completo (Oral)
Favoritar este trabajo
¿Cómo citar este artículo?
Resúmenes

Este trabajo aborda el Problema del Clic Máximo (PCM) en grafos, un conocido problema NP-Complete en teoría de grafos y optimización combinatoria. La mayoría de los algoritmos de bifurcación y enlace de última generación utilizan la heurística de intercalación glotona tanto para determinar el orden de ramificación como para obtener límites superiores. En muchos casos, las diferencias en los entornos computacionales pueden hacer que la comparación de resultados sea menos precisa. En este estudio, realizamos una comparación computacional del algoritmo MCS, presentado en el marco unificado para PCM por [Carmo y Züge (2012)], con dos algoritmos que utilizan el paralelismo de bits a través de la estructura Bitmap Roaring. Esta estructura demostró ser eficiente para aprovechar el paralelismo de bits propuesto para los algoritmos más recientes.

¡Comparte tus ideas o preguntas con los autores!

¿Sabías que el mayor estímulo en el desarrollo científico y cultural es la curiosidad? ¡Deje sus preguntas o sugerencias al autor!

Inicia sesión para interactuar

¿Tiene alguna pregunta o sugerencia? ¡Comparte tus comentarios con los autores!

Instituciones
  • 1 Universidade Federal do Ceará, Campus Quixadá
Eje Temático
  • 14. OC – Otimização Combinatória
Palabras Clave
Algoritmos en grafos
Clic máximo
Coloración de vértices
Mapas de bits rugientes
Ramificación y poda