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
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)
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