无向加权图的K点连通扩充算法

A K-Vertex-Connected Augmentation Algorithm for Undirected Weighted Graphs

本文首先研究了无权情况下的极小K点连通扩充算法;然后成功地将模拟退火方法应用于任意无向加权图的K点连通扩充问题,提出了一个O(ΩK|V|~4)的近似算法,为解决加权图的扩充问题提供了一种新途径.

In this paper, at first we present a minimal K-vertex-connected augmentation algorithm for unweighted graphs and then adopt simulated successfully in the K-vertexconnected augmentation of any undirected weightedgraphs. An approximation algorithm of O (OK|V|4) is presented, which provides a new approach for the augmentation problem of weighted graphs.