Maximum induced matching problem on hhd-free graphs

DOI10.1016/j.dam.2011.08.027zbMath1237.05166MaRDI QIDQ765362

R. Sritharan, Chandra Mohan Krishnamurthy

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.08.027

zbMATH Keywords

algorithm; induced matching; chordal; hhd-free

Mathematics Subject Classification ID

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.)

Related Items

Maximum induced matching of hexagonal graphs, Approximating weighted induced matchings, Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• On distance-3 matchings and induced matchings
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• LexBFS-orderings and powers of chordal graphs
• Duchet-type theorems for powers of HHD-free graphs
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Finding a maximum induced matching in weakly chordal graphs
• On the semi-perfect elimination
• A min-max property of chordal bipartite graphs with applications
• New results on induced matchings
• On brittle graphs
• Four classes of perfectly orderable graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph