#### Title

The maximum induced matching problem for some subclasses of weakly chordal graphs

#### Date of Award

2009

#### Degree Name

M.S. in Computer Science

#### Department

Department of Computer Science

#### Advisor/Chair

Advisor: R. Sritharan

#### Abstract

An induced matching in a graph is a set of edges such that no two edges in the set are joined by any third edge of the graph. An induced matching is maximum (MIM) if the number of edges in it is the largest among all possible induced matchings. It is known that finding the size of MIM in a graph is NP-hard even if the graph is bipartite. It is also known that the size of MIM in a chordal graph or in a weakly chordal graph can be computed in polynomial time. Specifically, the size of MIM can be computed in linear time for a chordal graph and in O(m³) time for a weakly chordal graph. This work demonstrates some algorithms for the maximum induced matching problem with complexity better than O(m³) for some subclasses of weakly chordal graphs. In particular, we show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time. Further, for two subclasses of hhd-free graphs, we show that the problem can be solved in better time than O(m²). The classes of graphs that we consider are either more general than chordal graphs or are a restriction of chordal b

#### Keywords

Graph theory, Computer science Mathematics

#### Rights Statement

Copyright 2009, author

#### Recommended Citation

Krishnamurthy, Chandra Mohan, "The maximum induced matching problem for some subclasses of weakly chordal graphs" (2009). *Graduate Theses and Dissertations*. 236.

https://ecommons.udayton.edu/graduate_theses/236