logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro