Largeur d'un ordre partiel

entrée : Un ordre partiel. C'est-à-dire un graphe dirigé $G(V,A)$ sans cycle.

sortie : trouver la taille de la plus grande anti-chaîne, c'est à le plus grand ensemble $S$ de sommets tel que qu'il n'existe pas $(u,v)\in S$ avec $(u,v)\in A$.

Problèmes

Complexité

en temps linéaire

Algorithme

* Produire un graphe bi-parti H(V,V',A'), avec V' étant une copie de V, et $(u,v')\in A'$ ssi $(u,v) \in A$.
* Calculer un couplage maximal bi-parti dans H.
* Compter le nombre de sommets non-couplés dans U. C'est la taille de la plus grande anti-chaîne dans G. Donc la largeur de l'ordre partiel G.

partOrderWidth.png

Références

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License