无向树图的k点连通最小扩充

THE MINIMUM AUGMENTATION OF A UNDIRECTED TREE GRAPH TO Ak-CONNECTED GRAPH

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。

The optimization problem of constructing k-connected graph from any undirected tree by adding a minimum set of edges is studied. An efficient algorithm with complexity of O(|V|~4) is presented. This algorithm constitutes a foundation for the computer aided design of reliable networks.