LIP6 2005/004

• Rapports de recherche «Une Condition Suffisante de Vivacité pour les Graphes d'événements généralisés»
• O. Marchetti, A. Munier-Kordon
• 17 pages - 24/05/2005 - document en - http://www.lip6.fr/lip6/reports/2005/lip6-2005-004.pdf 306 Ko
• Contact olivier.marchetti (at) nulllip6.fr
• Ancien Thème : ASIM
L'objectif de ce papier est de developper une condition suffisante de vivacité pour les graphes d'événements généralisés (GEG en abrégé) qui soit calculable en temps polynomial. Beaucoup de problèmes industriels peuvent être modélisés par un GEG et dans un contexte d'optimisation, un algorithme qui décide de la vivacité d'un GEG s'avère d'une grande utilité. Nous prouvons que tout GEG unitaire peut être transformé en un GEG normalisé tel quetoutes les valeurs des arcs adjacents à chaque transition dependent de la transition. Une condition suffisante de vivacité peut alors être simplement exprimée sur ce nouveau GEG et être polynomialement calculée. Nous démontrons que cette condition est aussi nécessaire dans le cas à deux transitions.