کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419452 | 683813 | 2012 | 7 صفحه PDF | دانلود رایگان |
We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m2)O(m2) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m3)O(m3). Then, 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.
► 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.
Journal: Discrete Applied Mathematics - Volume 160, Issue 3, February 2012, Pages 224–230