Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Complexite parametree Recherche de noyaux bornes inferieures
89 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Complexite parametree Recherche de noyaux bornes inferieures

-

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
89 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Complexite parametree (3) Recherche de noyaux - bornes inferieures Christophe PAUL (CNRS - LIRMM)

  • algorithmes de distillation et de composition conjecture

  • probleme ouvert

  • classe de complexite fpt

  • deduire des noyaux de tailles exponentiels

  • noyau polynomial


Informations

Publié par
Nombre de lectures 29
Langue Français

Extrait

Complexit´eparam´etr´ee(3) Recherchedenoyaux-bornesinfe´rieures
Christophe PAUL (CNRS - LIRMM)
Noyaux exponentiels Edge Clique-Cover Longest Path
Algorithmes de distillation et de composition Conjecture deou-distillation Non-existence de noyau polynomial Exemples
Transformationsparame´tre´espolynomiales D´efinitionetexemple R´eductionsnon-triviales
Compositionscrois´ees D´efinitionetthe´ore`mes Dominating set
Observation Lethe´ore`meprouvant,pourunprobl`emepara´tr´e(Q, κ), me l’e´quivalenceentrel’existenced’unnoyauetsonappartenance`ala classedecomplexite´FPT,nepermetquedede´duiredesnoyaux de tailles exponentiels.
I
Peut-onde´montrerquecertainsprobl`emesn’admettentpasde noyau polynomial ?
L exemple deEdge ’
I I
Clique-Cover
Un grapheG= (V,Ete`mer)unetrapak∈N Peut-oncouvrirlesar`etesEpar au pluskcliques ?
L’exemple deEdge
Clique-Cover
Theore`me[Gramm,Guo,H¨uffner,Niedermeier] ´ Edge Clique-Coveradmet un noyau de taille 2ksommets.
L’exemple deEdge
Clique-Cover
The´ore`me[Gramm,Guo,H¨uffner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
R`eglesder´eduction 1.sselremisistemmos´eolupprS 2.S’il existe deux sommetsxetytels queN[x] =N[y], supprimer l’un des deux sommets.
L’ emple deEdge ex
Clique-Cover
Th´eor`eme[Gramm,Guo,Hu¨ffner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
Preuve :Supposons qu’il existekcliquesC1. . .Ck A chaque sommetxon asscocie un verteurCdek
Observation :
C[x,i] = 1
⇐⇒
x
∈Ci
couvrantE. bits tel que
∀i∈[k]C[x,i] =C[y,i] ssiN[x] =N[y]
L’exemple deEdge
Clique-Cover
The´ore`me[Gramm,Guo,Hu¨ffner,Niedermeier] Edge Clique-Coveradmet un noyau de taille 2ksommets.
Preuve :Supposons qu’il existekcliquesC1. . .Ck A chaque sommetxon asscocie un verteurCdek
Observation :
C[x,i] = 1
⇐⇒
x
∈Ci
couvrantE. bits tel que
∀i∈[k]C[x,i] =C[y,i] ssiN[x] =N[y]
Probl`emeouvert Edge Clique-Coveradmet-il un noyau polynomial ?
  • 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