摘要
研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。
This paper describes the optimization of constructing a R-edge-connected graph from any given undirected graph go by adding a minimum set of edge. An efficient algorithm with a complexity of O(|V|~5) is presented, this paper presents a new method for reliable network design with the most effective use of existing network.
出处
《天津大学学报》
EI
CAS
CSCD
1990年第4期43-51,共9页
Journal of Tianjin University(Science and Technology)
基金
国家科委自然科学基金项目
关键词
无向图
最小扩充
R边连通
undirectrd graph, minimum augmentation, R-edge-connection
