Maximum induced matching problem on hhd-free graphs

DOI10.1016/J.DAM.2011.08.027MaRDI QIDQ765362zbMATH OpenOpenAlexFDO

Authors Chandra Mohan Krishnamurthy, R. Sritharan

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

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

Recommendations

• Maximum induced matchings in graphs
• Induced matchings in graphs of bounded maximum degree
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• On the induced matching problem in Hamiltonian bipartite graphs
• Graphs with maximal induced matchings of the same size
• Maximum induced matchings for chordal graphs in linear time
• Maximum induced matchings close to maximum matchings

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• A min-max property of chordal bipartite graphs with applications
• 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
• Duchet-type theorems for powers of HHD-free graphs
• Finding a maximum induced matching in weakly chordal graphs
• Four classes of perfectly orderable graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Irredundancy in circular arc graphs
• LexBFS-orderings and powers of chordal graphs
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• On brittle graphs
• On distance-3 matchings and induced matchings
• On the semi-perfect elimination
• The induced matching and chain subgraph cover problems for convex bipartite graphs

Cited in

(3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765362)