G. Melancon
Le Jeudi 15 Juin 2000 à 16h00
Salle de Conférences du LIX, École Polytechnique
G. Melançon
(CWI)
Génération aléatoire de graphes acycliques orientés
(en collaboration avec I. Dutour et M. Bousquet-Mélou / LaBRI, Bordeaux)
Résumé/Abstract :
Notre travail sur la génération aléatoire des ``dags''
est motivé par la nécessité de tester/mettre au point
des algorithmes de dessin ou des techniques de visualisation de ces graphes,
qui forment une classe relativement générale englobant un bon
nombre d'applications en visualisation d'information. Nos résultats
s'inspirent d'un article de Denise et al sur la génération de
graphes planaires et utilisent comme dans leur cas une chaîne de Markov.
Facile à implanter, elles nous a permis ensuite d'obtenir de
manière empirique une description de certaines statistiques utiles pour
la visualisation. Les techniques plus habituelles en combinatoire
énumérative permettent aussi de prédire l'allure moyenne
d'un dag. La chaîne de Markov a la bonne idée de pouvoir
être soumise à certains paramètres qui la rendent utile
pour le tirage aléatoire dans certaines sous-classes de dags, plus
utiles pour le dessin de graphes.