Dominating induced matchings in graphs without a skew star

DOI10.1016/j.jda.2013.11.002zbMath1298.05253OpenAlexW1996995804MaRDI QIDQ2447537

Nicholas Korpelainen, Christopher Purcell, Vadim V. Lozin

Publication date: 28 April 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.11.002

zbMATH Keywords

polynomial-time algorithmclique-widthdominating induced matchingefficient edge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (8)

Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

Cites Work

• Dominating induced matchings for \(P_7\)-free graphs in linear time
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• On stable cutsets in claw-free graphs and planar graphs
• Claw-free graphs. V. Global structure
• Efficient edge domination in regular graphs
• On maximal independent sets of vertices in claw-free graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Regular codes in regular graphs are difficult
• Treewidth for graphs with small chordality
• Independence and upper irredundance in claw-free graphs
• Perfect edge domination and efficient edge domination in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Dominating Induced Matchings
• On the Relationship Between Clique-Width and Treewidth
• Paths, Trees, and Flowers
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Dominating induced matchings in graphs without a skew star