Abstract : 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.
Résumé : 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
