Full list
You will be redirected to the institution’s website in order to read these documents.
-
2004 — Fractionally total colouring most graphsAbstract
Une coloration totale d’un graphe est le coloration des arêtes et des sommets telle que deux sommets adjacents ont des couleurs différentes, deux arêtes incidentes ont des couleurs différentes, et une arête a une couleur différente de celles des ses extrémités. Si nous formulons le problème de trouver le nombre chromatique total comme un programme linéaire entier, nous pouvons considérer la relaxation connue comme la coloration totale fractionnaire. Dans cette thèse nous présentons un algorithme pour calculer le nombre chromatique total d’un graphe en temps polynomial en moyenne. Nous présentons aussi un algorithme qui calcule asymptotiquement presque sûrement le nombre … Read more