The bridge-connectivity augmentation problem with a partition constraint

Abstract: In this paper, we consider the augmentation problem of an undirected graph with partitions of its vertices. The main issue is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, while maintaining the original partition constraint. To solve the problem, we propose a simple linear-time algorithm. To the best of our knowledge, the most efficient sequential algorithm runs in time. However, we show that it can also run in parallel time on an EREW PRAM using a linear number of processors, where is the number of vertices in the input graph. If a simple graph exists, our main algorithm ensures that it is as simple as possible. [Copyright &y& Elsevier]