Study of the article: " An O(k2n2) Algorithm to Find a k -partition in a k -connected Graph "
Résumé
This report study an O(k2n2) algorithm proposed to find k-partition in a k-connected graph. A counter-example is exhibited for which the execution of the algorithm might loop endlessly. Then a proof is given which generalize the counter-example for any k.
Ce rapport présente une étude d'un algorithme permettant de trouver une k-partition d'un graphe k-connexe avec une complexité en O(k2n2). Un contre-exemple est fourni, illustrant le fait que certaines exécutions de l'algorithme peuvent boucler indéfiniment. Finalement, une preuve qui généralise le contre-exemple pour une valeur de k quelconque est donnée
Origine : Fichiers produits par l'(les) auteur(s)