Maximum induced matching problem on hhd-free graphs

DOI10.1016/j.dam.2011.08.027zbMath1237.05166OpenAlexW2019670386MaRDI 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

algorithminduced matchingchordalhhd-free

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum induced matching problem on hhd-free graphs