Complexite parametree Decomposition et largeur arborescente

De
Publié par

Complexite parametree (6) Decomposition et largeur arborescente Christophe PAUL (CNRS - LIRMM)

  • complexite parametree

  • largeur arborescente

  • arete inutile

  • meta-theoreme

  • arbre

  • independant sur les arbres decomposition arborescente

  • algorithmes pour les graphes de largeur arborescente


Publié le : mardi 19 juin 2012
Lecture(s) : 34
Source : lirmm.fr
Nombre de pages : 87
Voir plus Voir moins
Complexit´eparam´etr´ee(6) De´compositionetlargeurarborescente
Christophe PAUL (CNRS - LIRMM)
Algorithmespourlesgraphesdelargeurarborescenteborn´ee EnsembleInde´pendantsur les arbres De´compositionarborescente EnsembleInde´pendentarepr´etm´rapatw(G) Chemin Hamiltonienarapte´mpe´rartw(G)
Calcul et approximation de la largeur arborescente
Theore`medeCourcelle ´ Logique du second ordre monadique Me´ta-the´o` reme
R´eduction`alargeurarborescenteborn´ee Obstructions Sommet/arˆeteinutile
EnsembleInd´ependantsre(avule´s)ruelasbr
EnsembleInde´pendantlrse)eusla´uv(esarbr
Ensemble
I ´ ndantselasbrerur)s´eluva( ndepe
Observations 1.seersnutudtbranurpa´eteraoutsommet 2.ntesposaexesconnadnepe´dmocedstnnsendioinesblemunldistinctesestunensembleind´ependant
Ensemble
Inde´pendantleur)s´eluva(ersasbr
Soitxla racine deTetx1. . .xlses fils: IwIS(T,x)ntc.noetandnnamtxandeipe´enseblemx IwIS(T,x)ensemble ind´ dant max. ne contenant pasx epen
Ensemble
Inde´pendantersasbr(luva)s´eleur
Soitxla racine deTetx1. . .xlses fils: IwIS(T,x)tnon.cnateanndaxtmblemnsepe´endeix IwIS(T,x)snespanoetantnmtxan.ce´ependanembleindx
wIS(T,x)
=
PwIS(T,xi) i[l]
Ensemble
Inde´pendantur)ssaleva(´eluerbrs
Soitxla racine deTetx1. . .xlses fils: IwIS(T,x)ielbmesndnepe´dn.caxtmanntnateonex IwIS(T,x)n.xanoceanetaptnsesnmebleind´ependantmx
wIS(T,x)
wIS
(T,x)
=
=
PwIS(T,xi) i[l] Pmax{wIS(T,xi),wIS(T,xi)} i[l]
D´ mposition arborescente eco
Uneteobercsneisitnoraopmoce´dd’un grapheG= (V,E) est une paire (T,{Xt:tT}) avecTest un arbre ettT,VtV, telle que
D´ecompositionarborescente
Uneetnecstisipoomreboaron´dced’un grapheG= (V,E) est une paire (T,{Xt:tT}) avecTest un arbre ettT,VtV, telle que I[couverture des sommets]xV,tTtel quexXt
D´ecompositionarborescente
Une´dceonarboreosmcpeonsteitid’un grapheG= (V,E) est une paire (T,{Xt:tT}) avecTest un arbre ettT,VtV, telle que I[couverture des sommets]xV,tTtel quexXt Isu]oc[evtrrudeseraeˆet(x,y)E,tTtel quex,yXt
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.