Maximum induced matching problem on hhd-free graphs. (English) Zbl 1237.05166
Summary: We show that the maximum induced matching problem can be solved on hhd-free graphs in \(O(m^{2})\) time; hhd-free graphs generalize chordal graphs and the previous best bound was \(O(m^{3})\). Then, we consider a technique used by A. Brandstädt and C. T. Hoàng [Algorithmica 52, No. 4, 440–447 (2008; Zbl 1171.68595)] 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.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Citations:
Zbl 1171.68595References:
| [1] | Abueida, A.; Busch, A. H.; Sritharan, R., A min-max property of chordal bipartite graphs with applications, Graphs and Combinatorics, 26, 301-313 (2010) · Zbl 1219.05136 |
| [2] | Brandstädt, A.; Dragan, F. F.; Nikolai, F., LexBFS-orderings and powers of chordal graphs, Discrete Mathematics, 171, 27-42 (1997) · Zbl 0880.05074 |
| [3] | Brandstädt, A.; Eschen, E. M.; Sritharan, R., The induced matching and chain subgraph cover problems for convex bipartite graphs, Theoretical Computer Science, 381, 260-265 (2007) · Zbl 1188.68209 |
| [4] | Brandstädt, A.; Hoàng, C. T., Maximum induced matchings for chordal graphs in linear time, Algorithmica, 52, 440-447 (2008) · Zbl 1171.68595 |
| [5] | Brandstädt, A.; Le, V. B.; Szymczak, T., Duchet-type theorems for powers of HHD-free graphs, Discrete Applied Mathematics, 177, 9-16 (1997) · Zbl 0887.05050 |
| [6] | Brandstädt, A.; Mosca, R., On distance-3 matching and induced matchings, Discrete Applied Mathematics, 159, 509-520 (2011) · Zbl 1210.05105 |
| [7] | Cameron, K., Induced matchings, Discrete Applied Mathematics, 24, 97-102 (1989) · Zbl 0687.05033 |
| [8] | Cameron, K., Induced matchings in intersection graphs, Discrete Mathematics, 278, 1-9 (2004) · Zbl 1033.05080 |
| [9] | Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics, 266, 133-142 (2003) · Zbl 1022.05064 |
| [10] | Chang, Jou-Ming, Induced matchings in asteroidal triple-free graphs, stability in graphs, and related topics, Discrete Applied Mathematics, 132, 67-78 (2004) · Zbl 1029.05120 |
| [11] | Chvátal, V., Perfectly ordered graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam), 63-65 · Zbl 0559.05055 |
| [12] | Chvátal, V.; Hoàng, C. T.; Mahadev, N. V.R.; de Werra, D., Four classes of perfectly orderable graphs, Journal of Graph Theory, 11, 481-495 (1987) · Zbl 0654.05032 |
| [13] | Fricke, G.; Laskar, R., Strong matchings on trees, Congressus Numerantium, 89, 239-243 (1992) · Zbl 0786.05065 |
| [14] | Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM Journal on Computing, 1, 180-187 (1972) · Zbl 0227.05116 |
| [15] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press · Zbl 0541.05054 |
| [16] | Golumbic, M. C.; Laskar, R. C., Irredundancy in circular arc graphs, Discrete Applied Mathematics, 44, 79-89 (1993) · Zbl 0783.05059 |
| [17] | Golumbic, M. C.; Lewenstein, M., New results on induced matchings, Discrete Applied Mathematics, 101, 157-165 (2000) · Zbl 0951.68104 |
| [18] | Hoàng, C. T.; Khouzam, N., On brittle graphs, Journal of Graph Theory, 12, 391-404 (1988) · Zbl 0653.05059 |
| [19] | Jamison, B.; Olariu, S., On the semi-perfect elimination, Advances in Applied Mathematics, 9, 364-376 (1988) · Zbl 0684.05020 |
| [20] | C.M. Krishnamurthy, The maximum induced matching problem for some subclasses of weakly chordal graphs, Masters Thesis, The University of Dayton, December 2009.; C.M. Krishnamurthy, The maximum induced matching problem for some subclasses of weakly chordal graphs, Masters Thesis, The University of Dayton, December 2009. |
| [21] | Rose, D. J.; Tarjan, R. E.; Leuker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5, 266-283 (1976) · Zbl 0353.65019 |
| [22] | Stockmeyer, L. J.; Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15, 14-19 (1982) · Zbl 0493.68039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
