1Complétion minimale en graphe d'intervalles en temps O n2

De
Publié par

1Complétion minimale en graphe d'intervalles en temps O(n2) Christophe Crespelle Université de Paris 6 Ioan Todinca Université d'Orléans

  • complétion en graphe

  • intérêt pour le calcul de la tree-width

  • intérêt pour le calcul de la path-width

  • structure du problème

  • problème etapproche


Publié le : mardi 19 juin 2012
Lecture(s) : 20
Source : lirmm.fr
Nombre de pages : 28
Voir plus Voir moins
1
Complétion minimale en graphe d’intervalles en temps O(n2)
Christophe Crespelle Université de Paris 6
Ioan Todinca Université d’Orléans
123...
Plan
Problème et approche
Structure du problème
Algorithme
2
I .  Paropbprlèomchee et
Edition de graphes
C
Complétion de graphes
omplétion dergpaehs
Classe de graphes
Classe de graphes
Graphes d’intervalles
3
Nombre minimum d’arêtes : NP-complet
Complétion en graphe triangulé
Intérêt pour le calcul de la tree-width
log n) [Heggernes et al. 2005] ou O(nm) [Rose et al. 1976]
Ensemble minimal d’arêtes: O(nαlog n) [
esI.   Pde graphlptéoi nC4mohecorppate emèlbor
Nombre minimum d’arêtes : NP-complet
Ensemble minimal d’arêtes: O(nαlog n) [Heggernes et al. 2005] ou O(nm) [Rose et al. 1976]
Intérêt pour le calcul de la path-width
Intérêt pour le calcul de la tree-width
Complétion en graphe triangulé
Nombre minimum d’arêtes : NP-complet
Complétion en graphe d’intervalles
O(nm) [Suchan et Todinca 2009]
Ensemble minimal d’arêtes: O(nm’) [Ohtsuki et al. 1981] [Heggernes et al. 2005]
plom5Crppaehcog arhpsetéoi nedblème etI.   Pro
téoimolpg ar nedI.  phesblèm Prorppate eehco6C
O(n2)
Intérêt pour le calcul de la path-width
Ensemble minimal d’arêtes: O(nαlog n) [Heggernes et al. 2005] ou O(nm) [Rose et al. 1976]
Intérêt pour le calcul de la tree-width
Complétion en graphe triangulé
Nombre minimum d’arêtes : NP-complet
Ensemble minimal d’arêtes: O(nm’) [Ohtsuki et al. 1981] [Heggernes et al. 2005]
O(nm) [Suchan et Todinca 2009]
Complétion en graphe d’intervalles
Nombre minimum d’arêtes : NP-complet
arg  ehpnidvretleal. sIPr  lèob7Complétion enechroppta eme
Hune complétion minimale de G
x
G
L’approche incrémentale
Complétion minimale de G+x
Complétion de H+x seulement avec desarêtes incidentes à x (un ensemble minimal)
Unecomplétion minimale du voisinagede x Telle que G+x soit un graphe d’intervalles
Résultat :
Temps O(n) ?
Nouveau Problème
Donnée :
Ungraphe d’intervallesG Un sommet x avec son voisinage N(x)
hp ednietvrlaelomplétion en grasCèleme atpporhce8I  . obPr
ra9Gesphi derntllavsebI.   Prboèleme atpporhc
e
c
d
e
a
c
e
a
b
d b c
a b c
d
d e c
123...
Plan
Problème et approche
Structure du problème
Algorithme
10
11oCpect restionmplénoéstnc fucitun aant gemerranborpemèl
a b x
a b c
Suppression de x dans un arrangement consécutif de G’
d e x
x
x
x
  . ruSturctdue II
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.