Multigraph augmentation under biconnectivity and general edge-connectivity requirements

✍ Scribed by Toshimasa Ishii; Hiroshi Nagamochi; Toshihide Ibaraki

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 247 KB
• Volume: 37
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.4

✦ Synopsis

Abstract

Given an undirected multigraph G = (V, E) and a requirement function r~λ~: () → Z^+^ (where () is the set of all pairs of vertices and Z^+^ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge‐connectivity and vertex‐connectivity between every pair x, y ∈ V become at least r~λ~(x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n^3^(m + n) log(n^2^/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((n____m + n^2^ log n) log n), in the case of the uniform requirement r~λ~(x, y)= 𝓁 for all x, y ∈ V. Furthermore, for the general r~λ~, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed 𝓁^*^ = max{r~λ~(x, y) | x, y ∈ V}. © 2001 John Wiley & Sons, Inc.