logo móvil
Contáctanos

Estudio computacional sobre un PTAS para el problema del conjunto dominante planar

Autores: Marzban, Marjan; Gu, Qian-Ping

Idioma: Inglés

Editor: MDPI

Año: 2013

Descargar PDF

Acceso abierto

Artículo científico
2013

Estudio computacional sobre un PTAS para el problema del conjunto dominante planar


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Problema del conjunto dominante
NP-duro
Esquema de aproximación
Grafos planares
Ratio de aproximación
Estudio computacional

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 26

Citaciones: Sin citaciones


Descripción
El problema del conjunto dominante es un problema central NP-duro en optimización combinatoria y teoría de grafos, y tiene muchas aplicaciones importantes. Baker [JACM 41,1994] introduce un marco basado en la descomposición de grafos planares exteriores para diseñar un esquema de aproximación de tiempo polinómico (PTAS) para una clase de problemas NP-duros en grafos planares. Se menciona que el marco se puede aplicar para obtener un algoritmo de aproximación de -constante para el problema del conjunto dominante planar. Mostramos que la proporción de aproximación lograda por la aplicación mencionada del marco no está limitada por ninguna constante para el problema del conjunto dominante planar. Modificamos la aplicación del marco para dar un PTAS para el problema del conjunto dominante planar. Con descomposiciones de grafos planares exteriores, el PTAS modificado tiene una proporción de aproximación . Utilizando descomposiciones de grafos planares exteriores, el PTAS modificado logra la proporción de aproximación en tiempo. Informamos un estudio computacional sobre el PTAS modificado. Nuestros resultados muestran que el PTAS modificado es práctico.

Otros recursos que podrían interesarte

Temas Virtualpro