logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro