Dominating induced matchings

DOI10.1007/978-3-642-02029-2_8MaRDI QIDQ3655141zbMATH OpenOpenAlexFDO

Authors D. M. Cardoso, Vadim 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

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

Recommendations

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Dominating induced matching in some subclasses of bipartite graphs
• Efficient edge domination in regular graphs
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Efficient edge domination on hole-free graphs in polynomial time

Cites work

• Efficient edge domination in regular graphs
• Efficient edge domination problems 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
• Induced matchings
• Linear time solvable optimization problems on graphs of bounded clique-width
• New results on induced matchings
• On maximum induced matchings in bipartite graphs
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• 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
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• The tree- and clique-width of bipartite graphs in special classes

Cited in

(14)

• On the dominating induced matching problem: spectral results and sharp bounds
• Some results on dominating induced matchings
• Dominating induced matchings in graphs without a skew star
• Efficient domination through eigenvalues
• Efficient edge domination on hole-free graphs in polynomial time
• Dominating induced matchings in graphs containing no long claw
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• scientific article; zbMATH DE number 866672 (Why is no real title available?)
• 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
• A simple matching domain with indifferences and a master list
• On the complexity of the dominating induced matching problem in hereditary classes of graphs

This page was built for publication: Dominating induced matchings

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