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

DOI10.1016/j.endm.2009.02.018zbMath1267.05265OpenAlexW2085235658MaRDI 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 algorithmdominating induced matchingefficient edge dominating set

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Modelling and solving the perfect edge domination problem ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Dominating induced matchings in graphs without a skew star ⋮ 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 ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ The Maximum Number of Dominating Induced Matchings

Cites Work

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

This page was built for publication: A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs