Complexite parametree Recherche de noyaux bornes superieures

De
Publié par

Complexite parametree (2) : Recherche de noyaux - bornes superieures Christophe PAUL (CNRS - LIRMM) October 5, 2011

  • regles de reduction pour vertex cover

  • recherche de noyaux - bornes superieures

  • reduction en couronne pour vertex cover

  • noyau lineaire pour le cluster editing

  • vertex cover

  • regles de reduction en sunflower analyse de la structure de la solution analyse


Publié le : mardi 19 juin 2012
Lecture(s) : 35
Tags :
Source : lirmm.fr
Nombre de pages : 98
Voir plus Voir moins

Complexite parametree (2) :
Recherche de noyaux - bornes superieures
Christophe PAUL
(CNRS - LIRMM)
October 5, 2011Un premier exemple: Vertex Cover
De nitions
Autres exemples de noyaux quadratiques
Regles de reduction en sunflower
Analyse de la structure de la solution par comptage
Programmation lineaire
Regles de reduction globales
Reduction en couronne pour Vertex Cover
Un noyau lineaire pour le Cluster Editing
Un noyau lineaire pour fast a l’aide de couplagesUn premier exemple: Vertex Cover
De nitions
Autres exemples de noyaux quadratiques
Regles de reduction en sunflower
Analyse de la structure de la solution par comptage
Programmation lineaire
Regles de reduction globales
Reduction en couronne pour Vertex Cover
Un noyau lineaire pour le Cluster Editing
Un noyau lineaire pour fast a l’aide de couplages2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)
3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)
Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)
Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)
2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)
2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)
3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)21. Le graphe reduit possede au plus k ar^etes.
22. Le graphe reduit possede au plus k + k sommets.
Preuve
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.22. Le graphe reduit possede au plus k + k sommets.
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.22. Le graphe reduit possede au plus k + k sommets.
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.
Si S est un Vertex Cover, alors toute ar^ete est incidente a
un sommet de S.
2Or d(x)6 k et ) k ar^etes au plus.Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.
22. Le graphe reduit possede au plus k + k sommets.

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.