任意有向圖的最小K邊連通擴充
THE MINIMUM AUGMENTATION OF AN ARBITRARY DIRECTED GRAPH TO A K-EDGE-CONNECTED DIRECTED GRAPH
-
摘要: 本文研究了以最小邊集擴充一個任意有向圖為K邊連通有向圖這一優(yōu)化問題。提出了一個復(fù)雜度O(|V|5)的有效算法。該算法為可靠網(wǎng)絡(luò)的計算機輔助設(shè)計打下了基礎(chǔ)。
-
關(guān)鍵詞:
- 圖論; 有向圖; 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. 默蒂著,吳望名,李念祖等譯,圖論及其應(yīng)用,科學出版社,1984年.[4]W. Mader, Annuals of Discrete Math., 3(1978), 145-164.[5]W. Mader, Europ. J. Combin., 3(1982), 63-67. -
計量
- 文章訪問數(shù): 2262
- HTML全文瀏覽量: 152
- PDF下載量: 464
- 被引次數(shù): 0
下載:
