【摘要】 提出了一个启发式迭代求解基于跳数约束的任意无向图R边连通扩充问题的算法.首先形成一个初始R边连通图,通过边交换和边替代来迭代降低扩充边集的费用,然后增加一些边满足跳数约束,再通过边置换和边删除来降低费用得到一个最优或较优的扩充图.给出了算例说明了算法的可行性.更多还原

【Abstract】 A heuristic iterative algorithm is presented to solve the problem of undirected graph’s R-edge-connectivity augmentation based on hop-constraint. Using this method, an initial R-edge-connectivity graph is formed and then the cost of new added edges is reduced by edge-exchanging and edge-replacing. Finally some edges meeting the demand of hops are added and an optimal or a better graph is obtained when the cost is reduced by edge-shifting and edge-deleting.更多还原