Pour le problème en question, il n'y a pas d'algorithme efficace (au sens d'une limite d'exécution polynomialement liée à la longueur de codage de l'entrée) par la classe d'exemples suivante.
Soit n un entier non négatif. Créez un graphe de tâche G=(V,E) avec n+2 nœuds comme suit. Soit s soit le noeud source, qui constitue la couche une, nous t_1,...,t_n être n noeuds intermédiaires à la couche deux, et soit t être un noeud terminal à trois couches, à savoir
V := { s } union { t_i : i in { 1,...,n } } union { t }
et relient couche une à la couche deux et la couche deux à trois couches, à savoir
E := { (s, t_i) : i in { 1,...,n } } union { (t_i, t) : { 1,...,n } }
qui signifie intuitivement que la source est connectée à toutes les tâches de toutes les tâches et sont reliées à la borne. Supposons que toutes les tâches t_{i}, pour chaque i in {1,...,n} aient le temps de traitement 1 ou 2; les temps de traitement de s et t n'ont pas d'importance. Cela signifie que potentiellement toutes les combinaisons de tâches t_{i}, pour chaque i in {1,...,n}, peuvent s'exécuter simultanément; cependant la cardinalité de l'ensemble de toutes les combinaisons de tâches t_i (qui est le power set de {t_1,...,t_n}) est 2^n, qui n'est pas polynomiale dans n. Cela dit, peut-être que la notion habituelle de 'temps d'exécution polynomial' ne s'applique pas ici, car la taille de la sortie n'est pas non plus polynomiale dans la taille de l'entrée.
Ne manquez-vous pas les cas où D se termine avant C? – m69
Je ne comprends pas exactement ce que vous regardez. Avez-vous besoin de calculer tous les ensembles indépendants de la fermeture de ce graphique? ou seulement les maximales? ou ai-je oublié quelque chose? Par exemple, pourquoi existe-t-il l'ensemble {H}, mais pas l'ensemble {D}? –
@DamienProt La liste des intersections ne semble pas complète. – m69