A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs

DOI10.1016/j.endm.2009.02.018zbMath1267.05265MaRDI QIDQ2839221

Nicholas Korpelainen

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.018

zbMATH Keywords

polynomial-time algorithm; dominating induced matching; efficient edge dominating set

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

The Maximum Number of Dominating Induced Matchings, Dominating induced matching in some subclasses of bipartite graphs, Combinatorial and spectral properties of König-Egerváry graphs, Exact algorithms for minimum weighted dominating induced matching, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, On the complexity of the dominating induced matching problem in hereditary classes of graphs, On the dominating induced matching problem: spectral results and sharp bounds, Modelling and solving the perfect edge domination problem, Dominating induced matchings in graphs without a skew star

Cites Work

• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Graph Classes: A Survey