|
Maintien dynamique des graphes d'intervalles| old_uid | 8478 |
|---|
| title | Maintien dynamique des graphes d'intervalles |
|---|
| start_date | 2010/03/31 |
|---|
| schedule | 10h30 |
|---|
| online | no |
|---|
| location_info | couloir 55-65, salle 554 |
|---|
| summary | Le problème abordé dans cet exposé est celui du maintien de la structure
d'un graphe d'intervalles subissant des modifications au cours du temps.
Ces modifications peuvent être le retrait ou l'ajout d'une arête ou d'un
sommet (avec les arêtes définissant son voisinage). A chaque pas de
l'algorithme, la donnée est constituée du graphe d'intervalles, donné
avec un modèle d'intersection, et d'une modification élémentaire. La
question posée est : le graphe est-il encore d'intervalles après cette
modification? Si la réponse est positive, l'algorithme met à jour le
modèle d'intersection, si elle est négative, il s'arrête.
Nous montrons comment traiter chacune des quatre opérations élémentaires
en temps O(n) en utilisant les PQ-arbres pour représenter l'ensemble des
modèles possibles d'un graphe d'intervalles. Cela fournit une vue
approfondie de la structure d'un graphe d'intervalle, et nous montrons
au passage une équivalence parfaite entre le PQ-arbre d'un graphe
d'intervalles et sa décomposition modulaire. |
|---|
| responsibles | Baerecke |
|---|
| |
|