Maximum induced matching problem on hhd-free graphs
| Autor: | R. Sritharan, Chandra Mohan Krishnamurthy |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Clique-sum Induced matching Chordal Applied Mathematics Interval graph Graph Algorithm Combinatorics Treewidth Indifference graph Pathwidth Chordal graph Discrete Mathematics and Combinatorics Maximal independent set Split graph hhd-free MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 160:224-230 |
| ISSN: | 0166-218X |
| Popis: | We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m2) time; hhd-free graphs generalize chordal graphs and the previous best bound was 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect