Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
<|reference_start|>Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time: A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the smallest number of edges to make a bipartite graph componentwise biconnected while preserving its bipartiteness. This algorithm has immediate applications for protecting sensitive information in statistical tables.<|reference_end|>
@article{hsu2001optimal,
    title={Optimal Augmentation for Bipartite Componentwise Biconnectivity in
  Linear Time},
    author={Tsan-sheng Hsu, Ming-Yang Kao},
    journal={arXiv preprint arXiv:cs/0102009},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0102009},
    primaryClass={cs.DS cs.DM}
}