Maximum Weight Matching-Based Algorithms for k-Edge-Connectivity Augmentation of a Graph
Satoshi Taoka, Takahiro Watanabe, Toshiya Mashima · 2005
The subject of the paper is to show that, by utilizing maximum-weight matching algorithms, we obtain heuristic algorithms of high capability for the k-edge-connectivity augmentation problem of graphs. The following points are shown by experimentally comparing the capabilities of eighteen algorithms for 4,175 graphs G' = (V, E') with 10/spl les/|V|/spl les/1400: (1) an existing algorithm, FSM, (previously proposed by us), based on an algorithm for finding a maximum-weight matching, produces the best solutions, while it becomes unrealistic when |V|>1000; (2) by utilizing a 2-approximation algorithm for the maximum-weight matching problem, a promising algorithm, HBD/sub a+/, is proposed, and it is shown that the second best solution (average 1.017 times that of FSM) is obtained in much shorter CPU time (average 0.1 times that of FSM).