Sun Lishan, Sun Yugeng, Yang Shan. THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH[J]. Journal of Electronics & Information Technology, 1990, 12(6): 593-599.
Citation:
Sun Lishan, Sun Yugeng, Yang Shan. THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH[J]. Journal of Electronics & Information Technology, 1990, 12(6): 593-599.
Sun Lishan, Sun Yugeng, Yang Shan. THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH[J]. Journal of Electronics & Information Technology, 1990, 12(6): 593-599.
Citation:
Sun Lishan, Sun Yugeng, Yang Shan. THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH[J]. Journal of Electronics & Information Technology, 1990, 12(6): 593-599.
The optimization problem of constructing a K-edge-connected directed graph from any given directed graph by adding a minimum set of edges is studied. An efficient algorithm with complexity of O(|V|5) is presented. This algorithm contributes a foundation for the computer aided design of reliable networks.
K. P. Eswaran, R. Ender Tarjan, SIAM J. Comput., 5(1976)4, 653-665.[2]Y. Kajitani, S. Veno, Neaworks, 16(1986), 181-197.[3]J. A.邦迪，U. S. R. 默蒂著,吴望名,李念祖等译,图论及其应用,科学出版社,1984年.[4]W. Mader, Annuals of Discrete Math., 3(1978), 145-164.[5]W. Mader, Europ. J. Combin., 3(1982), 63-67.
DownLoad: