Finding a maximum induced matching in weakly chordal graphs
by
Yingwen Tang
The University of Dayton
Coauthors: R. Sritharan (The University of Dayton)

An induced matching in a graph is a matching such that no two edges in the matching have any third edge between them in the graph. It is known that finding an induced matching of maximum cardinality in a graph is NP-Complete. We show that a maximum induced matching in a weakly chordal graph can be found in polynomial time. This generalizes some previously known results for the problem. This also demonstrates that a maximum induced matching in a chordal bipartite graph can be found in polynomial time while the problem is known to be NP-Complete for bipartite graphs in general.

Date received: April 9, 2001