logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro