Complexite parametree Recherche de noyaux bornes superieures

pefav - Christophe Paul

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

98 pages

Français

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

A propos
Informations
Extrait

Description

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

Sujets

Vertex cover

Informations

Publié par	pefav
Nombre de lectures	26
Langue	Français

Extrait

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.