Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Complexite parametree Decomposition et largeur arborescente
87 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Complexite parametree Decomposition et largeur arborescente

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
87 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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


Sujets

Complexité paramétrée

Informations

Publié par
Nombre de lectures 34
Langue Français

Extrait

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 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]
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Signaler un problème
playstore
appstore
facebook twitter instagram youtube

YouScribe

Le catalogue

Le service

Les conditions

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