Maximum induced matching problem on hhd-free graphs
From MaRDI portal
Publication:765362
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
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