Experiment-based Evaluation of Algorithm Performance for the 2- or 3-Vertex Connectivity Augmentation Problem

摘要

The k-vertex-connectivity augmentation problem (kVCA, for short) is defined by "Given a graph G = (V, E), a spanning subgraph G0 = (V, E') of G and a nonnegative weight function c : E→Z+, find a set E" C E - E' with the minimum total weight, such that G0 + E" = (V, E' U E") has at least k internally disjoint paths between any pair of vertices in V." Although these problems have wide application, such as constructing networks, it is known to be NP-complete. So some approximation or heuristic algorithms have been proposed. In this paper, we propose heuristic algorithms for 2VCA or 3VCA, and evaluate them through computational experiments.