Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time

Tsan-sheng Hsu, Ming-Yang Kao

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 s…