Displaying similar documents to “Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille”

Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille

Mustapha Aouchiche, Odile Favaron, Pierre Hansen (2009)

RAIRO - Operations Research

Similarity:

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme b ̲ n ≤ g ⊕ i ≤ b ¯ n où désigne la maille d'un graphe , un autre invariant parmi la distance moyenne l ¯ , l'index λ, l'indice de Randić et le nombre de domination , ⊕ désigne l'une des opérations +, -, ×, /, b ̲ n et b ¯ n des fonctions de l'ordre du graphe qui bornent l'expression g ⊕ i et sont atteintes pour tout (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

Le théorème fort des graphes parfaits

Gérard Cornuéjols (2005-2006)

Séminaire Bourbaki

Similarity:

Au début des années 60, Claude Berge a proposé deux conjectures sur les graphes parfaits. La première a été démontrée par Laci Lovász en 1972. La deuxième, dite conjecture forte des graphes parfaits, a fait couler beaucoup d’encre dans les 30 années qui ont suivi. Ce n’est qu’en 2002 qu’elle a été démontrée dans un article très impressionnant de 179 pages par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas. L’exposé présentera cette conjecture célèbre et donnera une idée...

Coloration de graphes : fondements et applications

Dominique de Werra, Daniel Kobler (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Les modèles classiques de coloration doivent leur notoriété en grande partie à leurs applications à des problèmes de type emploi du temps ; nous présentons les concepts de base des colorations ainsi qu’une série de variations et de généralisations motivées par divers problèmes d’ordonnancement dont les élaborations d’horaires scolaires. Quelques algorithmes exacts et heuristiques seront présentés et nous esquisserons des méthodes basées sur la recherche Tabou pour trouver des solutions...