Optimal Augmentation for Bipartite Componenentwise Biconnectivity in Linear Time

Tsan-sheng Hsu and Ming-Yang Kao

TR-IIS-96-010 (Fulltext)

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.