La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Recent Development of Graph Connectivity Augmentation Algorithms Développement récent d’algorithmes d’augmentation de la connectivité graphique

Hiroshi NAGAMOCHI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le problème d'augmentation de connectivité demande d'ajouter à un graphe donné le plus petit nombre de nouvelles arêtes afin que la connectivité des arêtes (ou des sommets) du graphe augmente jusqu'à une valeur spécifiée. k. Le problème a été largement étudié et plusieurs algorithmes efficaces ont été découverts. Nous étudions le développement récent des algorithmes pour ce problème. En particulier, nous montrons comment l'algorithme de coupe minimale dû à Nagamochi et Ibaraki est appliqué efficacement pour résoudre le problème d'augmentation de la connectivité des bords.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.372-383
Date de publication
2000/03/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
INVITED SURVEY PAPER
Catégories
Algorithmes graphiques

Auteurs

Mots-clés

Table des matières