Enumeration algorithms and graph theoretical models to address biological problems related to symbiosis

Nous montrons qu'il est possible d'à©numà©rer toutes les couvertures minimales de G en temps O([(M + 1) |S|] ^ [ log ((M + 1) |S|)]) o๠S est le nombre de couvertures minimales de G et M le nombre maximum des sous-graphes des chaà®nes dans une couverture minimale. Nous prà©sentons ensuite la relation entre le second problà¨me et le calcul de la dimension intervallaire d'un poset biparti. Nous donnons une interprà©tation de nos rà©sultats dans le contexte de la dimension d'ordre et la dimension intervallaire. En effet, nous pouvons calculer la dimension intervallaire d'un poset biparti P en O^*((2+ c)^p) o๠p est le nombre de de paires incomparables de P. Enfin, nous à©tendons ces rà©sultats au problà¨me du calcul de la dimension d'ordre. Par un rà©sultat classique en thà©orie des ordres (l'opà©ration "split" de Trotter), nous obtenons alors une procà©dure qui rà©sout ce problà¨me dans O^*((2+ c)^(p/2)). Pour amà©liorer nos rà©sultats sur la dimension d'ordre et faire mieux que O(sqrt{2}^p), i.e. le temps minimum pour exà©cuter la formule d'inclusion-exclusion sur laquelle ces rà©sultats sont basà©s, pour chaque poset nous introduisons un graphe associà© GCP, dit "graphe des paires critiques". De cette faà§on, nous obtenons deux algorithmes, un en espace exponentiel et un en espace polynomial. Ces algorithmes calculent la dimension d'ordre en temps 2^q et O(2.9977^q) respectivement o๠q est le nombre de paires critiques de P (intuitivement, les paires critiques sont les paires incomparables fondamen