Article ID Journal Published Year Pages File Type
436821 Theoretical Computer Science 2007 6 Pages PDF
Abstract

We present an O(n2)-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(m2).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics