The induced matching and chain subgraph cover problems for convex bipartite graphs
We present an O(n(2))-time algorithm for computing a maximum cardinality induced matching and a minimum cardinality cover by chain subgraphs for convex bipartite graphs. This improves the previous time bound of O(m(2)). (c) 2007 Elsevier B.V. All rights reserved.
induced matching convex bipartite graph chain cover