*Tsan-sheng Hsu and Ming-Yang Kao*

algorithm, linear time, bipartite graph augmentation, biconnectivity, data security

A graph is componentwise fully biconnected if every connected component either is an isolated vertex or is biconnected. We consider the problem of adding the smallest number of edges to make a bipartite graph componentwise fully biconnected while preserving its bipartiteness. This problem has important applications to protecting sensitive information in cross tabulated tables. In this paper, we present a linear time algorithm for this problem.