Un algoritmo distribuido de aproximación local 6 para el problema del conjunto dominante mínimo en grafos planares libres de triángulos
Autores: Wawrzyniak, Wojciech
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Un algoritmo distribuido de aproximación local 6 para el problema del conjunto dominante mínimo en grafos planares libres de triángulos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Distribuido
Aproximación
Proporción
Conjunto dominante
Grafos planares
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
En este documento, presentamos un nuevo algoritmo de aproximación distribuida para el problema del conjunto dominante mínimo en grafos planares libres de triángulos. El algoritmo opera en un número constante de rondas en el modelo LOCAL. Utilizando la técnica de montón, demostramos que nuestro algoritmo logra una relación de aproximación de 6, lo cual es una mejora significativa respecto a resultados anteriores para algoritmos distribuidos, donde la mejor relación de aproximación conocida era para cualquier . Mientras que los algoritmos secuenciales pueden lograr relaciones de aproximación por debajo de 5 para este problema, nuestro algoritmo distribuido logra la mejor relación de aproximación conocida en el modelo LOCAL. Proporcionamos una prueba detallada y análisis del algoritmo, que puede implementarse de manera distribuida.
Descripción
En este documento, presentamos un nuevo algoritmo de aproximación distribuida para el problema del conjunto dominante mínimo en grafos planares libres de triángulos. El algoritmo opera en un número constante de rondas en el modelo LOCAL. Utilizando la técnica de montón, demostramos que nuestro algoritmo logra una relación de aproximación de 6, lo cual es una mejora significativa respecto a resultados anteriores para algoritmos distribuidos, donde la mejor relación de aproximación conocida era para cualquier . Mientras que los algoritmos secuenciales pueden lograr relaciones de aproximación por debajo de 5 para este problema, nuestro algoritmo distribuido logra la mejor relación de aproximación conocida en el modelo LOCAL. Proporcionamos una prueba detallada y análisis del algoritmo, que puede implementarse de manera distribuida.