Study of the article: " An O(k 2 n 2 ) Algorithm to Find a k-partition in a k-connected Graph "

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
Keywords : Graph partitioning
Type de document :
Rapport
[University works] Université de bordeaux. 1994
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00998313
Contributeur : Ludovic Hofer <>
Soumis le : mercredi 10 février 2016 - 11:48:10
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : samedi 12 novembre 2016 - 15:53:01

Fichiers

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00998313, version 2

Collections

Citation

Olivier Baudon. Study of the article: " An O(k 2 n 2 ) Algorithm to Find a k-partition in a k-connected Graph ". [University works] Université de bordeaux. 1994. 〈hal-00998313v2〉

Partager

Métriques

Consultations de la notice

99

Téléchargements de fichiers

47