Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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]