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

Link to Full Text

Share

COinS