Advertisement
Published in:
2009 | OriginalPaper | Chapter
Dominating Induced Matchings
Authors : Domingos M. Cardoso, Vadim V. Lozin
Published in: Graph Theory, Computational Intelligence and Thought
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the problem of determining whether or not a graph
G
has an induced matching that dominates every edge of the graph, which is also known as
efficient edge domination
. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type.