Dominating induced matchings in graphs without a skew star

DOI10.1016/J.JDA.2013.11.002MaRDI QIDQ2447537zbMATH OpenOpenAlexFDO

Authors Nicholas Korpelainen, Vadim Lozin, Christopher Purcell

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

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

Recommendations

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Dominating induced matchings
• Dominating induced matchings in graphs containing no long claw
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

Cites work

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

Cited in

(12)

• On the dominating induced matching problem: spectral results and sharp bounds
• Finding dominating induced matchings in P₉-free graphs in polynomial time
• Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Dominating induced matchings in graphs containing no long claw
• 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 \(P_{10}\)-free graphs in polynomial time
• Graphs whose vertices of degree at least 2 lie in a triangle
• Dominating induced matchings and other graph parameters
• Perfect edge domination in P₆-free graphs and in graphs without efficient edge dominating sets
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

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

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