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
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
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.
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.