Ejercicio NP-Completitud
Publicado por Jorge (1 intervención) el 04/07/2022 11:44:08
Hola buenas, tengo dudas de la solución de este tipo de ejercicios NP-completitud, si alguien me pudiera dar una solución detallada con los pasos se lo agradecería.
El enunciado del ejercicio es:
Dado un conjunto U de objetos, una familia S={S1,...,Sn} de subconjuntos de U y un numero k, el problema SET-COVER consiste en determinar si existe una subfamilia T ⊆ S de a lo sumo k subconjuntos cuya unión es igual a U. Demostrar que el problema SET-COVER es NP-completo utilizando el problema de decisión de la cobertura de vértices PDCV.
El enunciado del ejercicio es:
Dado un conjunto U de objetos, una familia S={S1,...,Sn} de subconjuntos de U y un numero k, el problema SET-COVER consiste en determinar si existe una subfamilia T ⊆ S de a lo sumo k subconjuntos cuya unión es igual a U. Demostrar que el problema SET-COVER es NP-completo utilizando el problema de decisión de la cobertura de vértices PDCV.
Valora esta pregunta
0