Premium
Multigraph augmentation under biconnectivity and general edge‐connectivity requirements
Author(s) -
Ishii Toshimasa,
Nagamochi Hiroshi,
Ibaraki Toshihide
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.4
Subject(s) - multigraph , combinatorics , vertex (graph theory) , mathematics , undirected graph , graph , time complexity , connectivity , directed graph , function (biology) , discrete mathematics , evolutionary biology , biology
Abstract Given an undirected multigraph G = ( V , E ) and a requirement function r λ : ( V 2 ) → Z + (where ( V 2 ) 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.