Maximum Induced Matching Problem on HHD-Free Graphs

Author(s)

Chandra Mohan Krishnamurthy, University of Dayton
R. Sritharan, University of DaytonFollow

Document Type

Article

Publication Date

2-2012

Publication Source

Discrete Applied Mathematics

Abstract

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). hen, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.

Highlights

• Faster algorithm to find a largest induced matching in an hhd-free graph is given.
• For a superclass of chordal graphs, a linear time algorithm for the problem is given.
• Examples are presented to demonstrate the tightness of results.

Inclusive pages

224-230

ISBN/ISSN

0166-218X

Comments

Permission documentation on file.

Copyright

Copyright © 2011, Elsevier

Publisher

Elsevier

Volume

160

Peer Reviewed

yes

Issue

3

eCommons Citation

Krishnamurthy, Chandra Mohan and Sritharan, R., "Maximum Induced Matching Problem on HHD-Free Graphs" (2012). Computer Science Faculty Publications. 168.
https://ecommons.udayton.edu/cps_fac_pub/168