Smallest Bipartite Bridge-Connectivity Augmentation |
| |
Authors: | Pei-Chi Huang Hsin-Wen Wei Wan-Chen Lu Wei-Kuan Shih Tsan-sheng Hsu |
| |
Affiliation: | (1) EECS Rm 730, Department of Computer Science, National Tsing-Hua University, 101, Section 2, Kuang-Fu Road, Hsinchu, 30013, Taiwan;(2) Institute of Information Science, Academia Sinica, Nankang, Taipei, Taiwan |
| |
Abstract: | 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 does 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+nlog 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.
H.-W. Wei, W.-C. Lu and T.-s. Hsu research supported in part by NSC of Taiwan Grants 94-2213-E-001-014, 95-2221-E-001-004
and 96-2221-E-001-004. |
| |
Keywords: | 2-edge-connectivity Bridge-connectivity Data security Bipartite graph augmentation |
本文献已被 SpringerLink 等数据库收录! |
|