Complexite parametree Recherche de noyaux bornes superieures
98
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
98
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- 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é par
Langue
Français
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.
