Complexite parametree Decomposition et largeur arborescente

pages

Français

Documents

Écrit par
Christophe Paul

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

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

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

Complexité paramétrée

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.seersnutu’dtbranurpa´eteraoutsommet 2.ntesposaexesconnadnepe´dmocedstnns’endioinesblemunl’ distinctesestunensembleind´ependant

Ensemble

Inde´pendantleur)s´eluva(ersasbr

Soitxla racine deTetx1. . .xlses ﬁls: 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 ﬁls: 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 ﬁls: 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]

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts

Complexite parametree Decomposition et largeur arborescente

YouScribe

Le catalogue

Le service

Les conditions