Finding all maximally-matchable edges in a bipartite graph

We consider the problem of finding all maximally-matchable edges in a bipartite graph G = (V, E), i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time O(n + m) (where n = vertical bar V vertical bar and m = vertical bar E vertical bar). Hence, the time complexity of finding all maximally-matchable edges reduces to that of finding a single maximum matching, which is O(n(1/2)m) (Hoperoft and Karp [12]), or O((n/log n)(1/2)m) for dense graphs with m = Theta(n(2)) (Alt et al. [2]). This time complexity improves upon that of the best known algorithms for the problem, which is O(nm) (Costa [5] for bipartite graphs, and Carvalho and Cheriyan [6] for general graphs). Other algorithms for solving that problem are randomized algorithms due to Rabin and Vazirani [15] and Cheriyan [3], the runtime of which is (O) over tilde (n(2.376)). Our algorithm, apart from being deterministic, improves upon that time complexity for bipartite graphs when in = O(n(r)) and r < 1.876. In addition, our algorithm is elementary, conceptually simple, and easy to implement. (C) 2011 Elsevier B.V. All rights reserved.