Projet ANR graal - Réunions"Décompositions de Graphes et Algorithmes"Accueil | Réunions | Participants | Publications | Contacts2-4 avril 2007, LIRMM (Montpellier) Lundi 2 avril
Références:
C. Crespelle et C. Paul. Fully
dynamic algorithm for modular decomposition and recognition of
permutation graphs. In 31st International Workshop on Graph Theoretical
Concepts in Computer Science - WG, number 3787 in Lecture Notes in
Computer Science, pages 38--48, 2005.
C. Crespelle. Fully dynamic representations of interval graphs. Submitted, 2007. Nous
faisons un parallèle entre la décomposition modulaire et
la décomposition en coupes en présentant ces deux
méthodes à l'aide d'arbres étiquetés par
des graphes. Dans les deux cas, les graphes totallement
décomposables admettent une caractérisation
incrémentale simple. Pour la décomposition modulaire,
cette caractérisation des cographes, dûe à Corneil,
Pearl et Stewart, permet un algorithme incrémental de
reconnaissance
des cographes en O(d) par ajout de sommets. Nous montrons qu'il en est
de même pour la décomposition en coupe et les graphes
distance héréditaires.
Référence:
E. Gioan et C. Paul. Dynamic distance hereditary graphs using split decomposition. RR-LIRMM 07-007, 2007.
Tout comme
la décomposition modulaire, la décomposition en coupe de
Cunnigham peut être définie par des formules de la logique
du second-ordre monadique. Cette construction s'applique aux graphes
d'intersections des cordes d'un cercle.
Références: B. Courcelle. The monadic second-order logic of graphs XVI : Canonical Graph Decompositions, Logical Methods in Computer Science 2 (2006) 1-46 B. Courcelle. Circle graphs and Monadic Second-order logic. Soumis.
Mardi 3 avril
La
décomposition bi-joint est une décomposition de graphes
non orientés généralisant la décomposition
modulaire. On montra une forte relation entre cette
décomposition et la décomposition modulaire au travers du
"Seidel switch". Cette relation nous donnera différentes
caractérisations des graphes entièrement
décomposables, et un algorithme linéaire de
décomposition. On donnera également un
théorème de décomposition des graphes sans gem et
co-gem induits. Dans la seconde partie, on présentera une
famille de décompositions de 2-structures
généralisant la décomposition modulaire. La
décomposition bi-joint des graphes non orientés et des
tournois en sont des cas particuliers. On verra que deux
différentes décompositions de cette famille
généralisent la décomposition bi-joint sur les
graphes orientés. Enfin on verra que toutes ces
décompositions peuvent être calculées en temps
O(n^3) (pour une décomposition fixée dans la famille).
Références: F. de Montgolfier et M. Rao. Bipartities families and the bi-join decomposition. M. Rao. New decompositions of 2-structures.
Oum et Seymour ont introduit la
"rank-width" comme paramètre de "largeur" permettant
d'approximer la largeur de clique. Contrairement à la
largeur de clique, la "rank-width" n'est pas définie en terme
d'opérations de construction de graphes. Nous proposons une
caractérisation algébrique de cette notion. Dans certains
algorithmes, il est nécessaire de disposer d'une
décomposition équilibrée (Courcelle, Vanicat et
Twigg pour la largeur de clique, Bodlaender pour la
décomposition arborescente). Nous proposons une
méthode générale pour équilibrer des
termes. Ceci nous permet d'unifier les théorémes
d'equilibrage connus et de proposer un théorème
d'équilibrage pour la "rank-width".
Mercredi 4 avril
Référence:
Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 188-197, 2006.
Nous
présentons tout d'abord différents résultats pour
calculer une application de manière optimale en ressources
mémoires. Le simple cas des applications linéaires permet
d'obtenir une décomposition des graphes dirigés par
une seule opération : "la complémentation locale
relative". Par ailleurs ceci permet de définir pour tout graphe
dirigé G d'ordre N, un nouveau graphe G^C de même ordre N
et qui construit le graphe G de départ par un
procédé séquentiel partant du graphe simplement
réflexif. Il est remarquable que cette notion de "constructeurs
itérés" forme elle même un cycle. Ensuite, pour
améliorer les bornes actuelles, nous introduisons la notion de
graphes fonctionnels qui sont des supports de calculs optimaux de
toutes les applications sur des ensembles finis, et ceci par un jeu
déterministe sur les sommets et les arcs. Un point remarquable :
si un graphe G permet de calculer toutes les bijections en exactement K
étapes, alors il permet de calculer toutes les applications en
K' étapes. La conjecture centrale restante est : K'=K+1.
|