Dominating Induced Matchings
Dominating Induced Matchings
复制标题
主导诱导匹配
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
V. Lozin
中科院分区：
文献类型：
--
作者：
D. Cardoso;V. Lozin
我们研究的问题，确定是否有一个诱导匹配，支配图的每一边，这也被称为有效的边支配。这个问题在一般情况下是NP-完全的，在某些限制域中也是NP-完全的，例如二部图或正则图。在本文中，我们确定了一个图形参数的问题的复杂性是明智的，并产生负（棘手的）和积极的（在多项式时间内可解）类型的结果。
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.