TR-IIS-06-016
** ** Fulltext

**Smallest
Bipartite Bridge-connectivity Augmentation
**

Pei-Chi Huang, Hsin-Wen
Wei, Wan-Chen Lu, Wei-Kuan Shih and Tsan-sheng Hsu

This paper addresses two augmentation problems related
to bipartite graphs. The first, a fundamental graph-theoretical problem, 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, and still bipartite.
The second problem, which arises naturally from research on the security of
statistical data, is how to add edges so that the resulting graph is simple
and dose not contain any bridges. In both cases, after adding edges, the graph
can be either a simple graph or, if necessary, a multi-graph. Our approach then
determines whether or not such an augmentation is possible.

We propose a number of simple linear-time algorithms to solve both problems.
Given the well-known bridge-block data structure for an input graph, the algorithms
run in O(log n) parallel time on an EREW PRAM using a linear number of processors,
where n is the number of vertices in the input graph. We note that there is
already a polynomial time algorithm that

solves the first augmentation problem related to graphs with a given general
partition constraint in O(n(m+n log n) log n) time, where m is the number of
distinct edges in the input graph. We are unaware of any results for the second
problem.