Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs

Krishnamurthy, Chandra Mohan

Abstract Details

2009, Master of Computer Science (M.C.S.), University of Dayton, Computer Science.
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(m3) time for a weakly chordal graph. This work demonstrates some algorithms for the maximum induced matching problem with complexity better than O(m3) 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(m2) time. Further, for two subclasses of hhd-free graphs, we show that the problem can be solved in better time than O(m2). The classes of graphs that we consider are either more general than chordal graphs or are a restriction of chordal bipartite graphs.
R Sritharan, PhD (Advisor)
Barbara A. Smith, PhD (Committee Member)
Dale Courte, PhD (Committee Member)
94 p.

Recommended Citations

Citations

  • Krishnamurthy, C. M. (2009). The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs [Master's thesis, University of Dayton]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006

    APA Style (7th edition)

  • Krishnamurthy, Chandra Mohan. The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs. 2009. University of Dayton, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006.

    MLA Style (8th edition)

  • Krishnamurthy, Chandra Mohan. "The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs." Master's thesis, University of Dayton, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006

    Chicago Manual of Style (17th edition)