任意有向图的最小K边连通扩充
THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH
-
摘要: 本文研究了以最小边集扩充一个任意有向图为K边连通有向图这一优化问题。提出了一个复杂度O(|V|5)的有效算法。该算法为可靠网络的计算机辅助设计打下了基础。
-
关键词:
- 图论; 有向图; K边连通有向图
Abstract: 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. -
计量
- 文章访问数: 2254
- HTML全文浏览量: 149
- PDF下载量: 464
- 被引次数: 0
下载:
