A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs

DOI10.1016/J.ENDM.2009.02.018MaRDI QIDQ2839221zbMATH OpenOpenAlexFDO

Authors 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

dominating induced matchingefficient edge dominating setpolynomial-time algorithm

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) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Dominating induced matching in some subclasses of bipartite graphs
• Dominating induced matchings in graphs containing no long claw
• Dominating induced matching in some subclasses of bipartite graphs
• Finding dominating induced matchings in P₉-free graphs in polynomial time

Cites work

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

Cited in

(11)

• On the dominating induced matching problem: spectral results and sharp bounds
• Modelling and solving the perfect edge domination problem
• Exact algorithms for dominating induced matching based on graph partition
• Dominating induced matchings in graphs without a skew star
• Dominating induced matchings in graphs containing no long claw
• The Maximum Number of Dominating Induced Matchings
• Combinatorial and spectral properties of König-Egerváry graphs
• Exact algorithms for minimum weighted dominating induced matching
• Dominating induced matching in some subclasses of bipartite graphs
• 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

This page was built for publication: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs

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