Complexite parametree Recherche de noyaux bornes superieures

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 (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

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

Vertex cover

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.