Codage des voisinages et parcours en largeur en temps O n des graphes d'intervalles et de permutations

Publié par


  • mémoire


Montpellier – 05/11/2009 – JGA'09 Codage des voisinages et parcours en largeur des graphes d'intervalles et de permutation Christophe Crespelle, Philippe Gambette

  • graphes de permutation

  • requêtes sur le graphe

  • encodage des voisinages dans les graphes d'intervalles

  • stockage du graphe en mémoire

  • temps de réponse réduit


Publié le : mardi 19 juin 2012
Lecture(s) : 25
Tags :
Source : lirmm.fr
Nombre de pages : 32
Voir plus Voir moins
re
 
Paln
·Problème et définitions
·Encodage des voisinages dans les graphes d'intervalles et les graphes de permutation
·Recherche en largeur enO(n) dans les graphes d'intervalles et les graphes de permutation
 
 
Paln
·Problème et définitions
·Encodage des voisinages dans les graphes d'intervalles et les graphes de permutation
Recherche en largeur enO(n) dans les graphes · d'intervalles et les graphes de permutation
 
 
d  emespsn eéropage ncodactTcompel rus sEehparg eirmométeuêeq R
 
 
Algorithmes sur les grands graphes
duréitCotS akcoheapn  e dgegru tnxeet
Bon encodage vis à vis des requêtes d'adjacence : Nombreuses classes de graphes d'intersection
Algorithmes sur les grands graphes
 
 
itoCtnxemémo en apheu gregd coak tSetnse rédu de répocaTtmespga eocpmeEphodncler ra getêuus seriqeR 
émome  nR qeries suuête grar ledocnEehppmoc egapsemtTacporée  doCtnxeettS kaoc dgegru heapite nsduréenacdj'aO(n  eceeRd setêuqs sscent boriuneosmm)1 2daajte s
 
3
v1G v v2
Bon encodage vis à vis des requêtes d'adjacence : Nombreuses classes de graphes d'intersection Exemple : graphes d'intervalles :
Algorithmes sur les grands graphes
= {[0,2],[1,3],[3,4]}
Encodage en O(n)
I1I  I3     2 1 Î [0,2]: 1et2adjacents  
tre.inl's an dseluncua'l ed ellavretrvalintee l'ne dtsi nue  e'leld 
Bon encodage vis à vis des requêtes d'adjacence : Nombreuses classes de graphes d'intersection
Bon encodage vis à vis des requêtes de voisinage ?
 
 
Algorithmes sur les grands graphes
têses ruer eRuqen mémoi graphe gakcud eotS etextContpénoedr déiuesr paom cges mpTectparg el adocnEeh
ckage du Stoesêtur s requRem neioméarg  ehpmps ctTeompage cocadehnErgpal  etiudér esnopér edextteonC
Algorithmes sur les grands graphes
Bon encodage vis à vis des requêtes d'adjacence : Nombreuses classes de graphes d'intersection
 
v1G v3 v2
I   I2I3  1
 
Encodage en O(n)
Requêtes de voisinage en O(n) O(d) ?
Bon encodage vis à vis des requêtes de voisinage ? Exemple : graphes d'intervalles :
= {[0,2],[1,3],[3,4]}
 
Algorithmes sur les grands graphes
 
Bon encodage vis à vis des requêtes de voisinage ? Encodage enO(n)avec requêtes de voisinage enO(d) pour graphes d'intervalles et graphes de permutation. → extension aux graphes quelconques par complétion → exploitation algorithmique de la structure des voisinages
Bon encodage vis à vis des requêtes d'adjacence : Nombreuses classes de graphes d'intersection
ocStgeka exteoCtnle gsur eEncraph eocdogaTtmepmcaapgru  dmén  eheR eriom setêuqe dpsrée nsporée tiud
Plan
·Problème et définitions
·Encodage des voisinages dans les graphes d'intervalles et les graphes de permutation
·Recherche en largeur enO(n) dans les graphes d'intervalles et les graphes de permutation
 
 
xeses biconv Grapheserporp sellavrent'i desphra Geerllanuthc epporne aU
Paramètres non bornés pour graphes d'intervalles et graphes de permutation : contiguïté : Ω(logn) linéarité : Ω(logn/ log logn)
x
x
Généralisation, 2 paramètres : autoriser plusieurs intervalles :contiguïté autoriser plusieurs ordres :linéarité
 
 
N(x)
N[x]
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.