Un algoritmo de aproximación para una variante del problema de conjunto dominante
Autores: Wang, Limin; Wang, Wenqi
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Un algoritmo de aproximación para una variante del problema de conjunto dominante
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Problema del conjunto dominante total
Problema del conjunto dominante
Algoritmo de aproximación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
En este documento, consideramos una variante del problema del conjunto dominante, es decir, el problema del conjunto dominante total. Dado un grafo no dirigido , un subconjunto de vértices se llama un conjunto dominante total si cada vértice en está conectado a al menos un vértice en . Basado en técnicas de relajación LP, este documento proporciona un algoritmo de aproximación distribuido para el problema del conjunto dominante total en grafos generales. El algoritmo presentado obtiene un conjunto dominante total fraccional que es, como máximo, veces el tamaño de la solución óptima a este problema, donde es un entero positivo y es el grado máximo de . El tiempo de ejecución de este algoritmo es constante en rondas de comunicación bajo la suposición de un modelo de comunicación síncrona.
Descripción
En este documento, consideramos una variante del problema del conjunto dominante, es decir, el problema del conjunto dominante total. Dado un grafo no dirigido , un subconjunto de vértices se llama un conjunto dominante total si cada vértice en está conectado a al menos un vértice en . Basado en técnicas de relajación LP, este documento proporciona un algoritmo de aproximación distribuido para el problema del conjunto dominante total en grafos generales. El algoritmo presentado obtiene un conjunto dominante total fraccional que es, como máximo, veces el tamaño de la solución óptima a este problema, donde es un entero positivo y es el grado máximo de . El tiempo de ejecución de este algoritmo es constante en rondas de comunicación bajo la suposición de un modelo de comunicación síncrona.