Vertex cover reconfiguración y más allá
Autores: Mouawad, Amer E.; Nishimura, Naomi; Raman, Venkatesh; Siebertz, Sebastian
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Vertex cover reconfiguración y más allá
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Cubierta de vértices
Reconfiguración
Problema VCR
Complejidad
Grafos
Dificultad
Tratable
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 43
Citaciones: Sin citaciones
En el problema de Reconfiguración de Cubrimiento de Vértices (VCR), dado un grafo , enteros positivos y y dos cubrimientos de vértices y de tamaño como máximo , determinamos si se puede transformar en mediante una secuencia de adiciones o eliminaciones de vértices de tamaño como máximo , de modo que cada operación resulte en un cubrimiento de vértices de tamaño como máximo . Motivados por resultados que establecen la -dificultad de VCR cuando está parametrizado por , delimitamos la complejidad del problema restringido a varias clases de grafos. En particular, mostramos que VCR sigue siendo -difícil en grafos bipartitos, es -difícil, pero tratable por parámetros fijos en grafos (regulares) de grado acotado y más generalmente en grafos de densidad nula y es resoluble en tiempo polinómico en árboles y (con algunas restricciones adicionales) en grafos cacto.
Descripción
En el problema de Reconfiguración de Cubrimiento de Vértices (VCR), dado un grafo , enteros positivos y y dos cubrimientos de vértices y de tamaño como máximo , determinamos si se puede transformar en mediante una secuencia de adiciones o eliminaciones de vértices de tamaño como máximo , de modo que cada operación resulte en un cubrimiento de vértices de tamaño como máximo . Motivados por resultados que establecen la -dificultad de VCR cuando está parametrizado por , delimitamos la complejidad del problema restringido a varias clases de grafos. En particular, mostramos que VCR sigue siendo -difícil en grafos bipartitos, es -difícil, pero tratable por parámetros fijos en grafos (regulares) de grado acotado y más generalmente en grafos de densidad nula y es resoluble en tiempo polinómico en árboles y (con algunas restricciones adicionales) en grafos cacto.