Worldlex Wiki Cette technique a été inventée par Reed, Smith et Vetta pour démontrer que le problème de la transversale des cycles impairs était résoluble en temps de tractabilité à paramètre fixe . Elle est aujourd'hui considérée comme l'une des techniques fondamentales en algorithmique paramétrée.
La compression itérative a été utilisée avec succès dans de nombreux problèmes, par exemple la résolution transversale de cycles impairs (voir ci-dessous) et la bipartition d'arêtes , l'ensemble de sommets de rétroaction et la suppression de sommets de cluster. Elle a également été utilisée avec succès pour des algorithmes exacts en temps exponentiel pour les ensembles indépendants .
problèmes de graphes paramétrés dont les entrées sont un graphe entier naturel sous-graphes induits : si une solution de taille recherche exponentielle externe ou une recherche séquentielle de la valeur optimale de cycle impair transversal d'un graphe est un ensemble de sommets qui, une fois supprimés, rendent le graphe biparti. Dans leur article original, Reed et al. ont proposé un algorithme de compression itératif permettant de déterminer si un graphe possède un cycle impair transversal de taille inférieure ou égale à k , en un temps O (3k kmn ) . Plus tard, Lokshstanov, Saurabh et Sikdar ont proposé un algorithme plus simple, également basé sur la compression itérative [6]. de flot maximal et de coupe minimale .La couverture de sommets est un autre exemple d'application de la compression itérative. Dans ce problème, un graphe
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.Plus d articles de Worldlex Wiki