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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hiroshi NAGAMOCHI, "Recent Development of Graph Connectivity Augmentation Algorithms" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 372-383, March 2000, doi: .
Abstract: The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_372/_p
Copier
@ARTICLE{e83-d_3_372,
author={Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Recent Development of Graph Connectivity Augmentation Algorithms},
year={2000},
volume={E83-D},
number={3},
pages={372-383},
abstract={The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.},
keywords={},
doi={},
ISSN={},
month={March},}
Copier
TY - JOUR
TI - Recent Development of Graph Connectivity Augmentation Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 372
EP - 383
AU - Hiroshi NAGAMOCHI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.
ER -