Dominating Induced Matchings

DOI10.1007/978-3-642-02029-2_8zbMath1194.05114OpenAlexW1486102037MaRDI QIDQ3655141

Domingos Moreira Cardoso, Vadim V. Lozin

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_8

zbMATH Keywords

polynomial-time algorithmdominating 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)

Efficient domination through eigenvalues ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Dominating induced matchings in graphs without a skew star ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ The Maximum Number of Dominating Induced Matchings

Cites Work

• Unnamed Item
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Efficient edge domination in regular graphs
• Induced matchings
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Regular codes in regular graphs are difficult
• Perfect edge domination and efficient edge domination in graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On maximum induced matchings in bipartite graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• New results on induced matchings
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Dominating Induced Matchings