Sean conjuntos que pueden tener elementos en común. Estoy buscando un conjunto X más pequeño tal que ∀ i , .
¿Este problema tiene un nombre? ¿O se reduce a algún problema conocido?
En mi contexto describo los ciclos elementales de un componente fuertemente conectado, y estoy buscando un conjunto más pequeño de vértices X que interseque todos los ciclos.
Si consideramos S1, S2 ... Sn como secuencias diferentes y si necesitamos la subsecuencia más larga que es común en estas secuencias, este tipo de problema se denomina "Subsecuencia común más larga (LCS)". Podemos alterar la condición para convertirla en una subsecuencia común más pequeña que encontrará un elemento único del conjunto como una subsecuencia más pequeña.
Vea ejemplos de programación dinámica, obtendrá los detalles ...
fuente