Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time

Simple item page
dc.creatorHsu, Tsan-sheng
dc.creatorKao, Ming-Yang
dc.date2001-02-10
dc.date.accessioned2026-07-07T03:16:56Z
dc.date.available2026-07-07T03:16:56Z
dc.descriptionA 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.
dc.descriptionA preliminary version appeared in T. Asano, Y. Igarashi, H. Nagamochi, S. Miyano, and S. Suri, editors, Lecture Notes in Computer Science 1178: Proceedings of the 7th Annual International Symposium on Algorithms and Computation, pages 213--222. Springer-Verlag, New York, NY, 1996
dc.identifierhttps://arxiv.org/abs/cs/0102009
dc.identifierhttp://arxiv.org/abs/cs/0102009
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30539
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectF.2.2; G.2.2
dc.titleOptimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
dc.typetext

Files

Collections

arXiv