An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
复制标题
DOI：
10.1007/978-3-642-45030-3_52
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Min Chih Lin;Michel J. Mizrahi;J. Szwarcfiter
中科院分区：
文献类型：
--
作者：
Min Chih Lin;Michel J. Mizrahi;J. Szwarcfiter
设一个图G的一条边支配它自己，并且每一条边共享它的一个顶点，则图G =（V，E）的一个边支配集是边E ′ ∈ E支配G的所有边的子集。特别地，如果G的每条边都恰好被E ′的一条边支配，则E ′是支配诱导匹配。已知不是每个图都允许支配诱导匹配，而判定它是否允许支配诱导匹配的问题是NP-完全的。本文研究了带权边图的最小权控制诱导匹配的求法和控制诱导匹配的计数问题。我们描述了一个精确的算法，一般图，运行在O *（1.1939n）时间和多项式（线性）空间，解决这些问题。这改善了现有的精确算法的问题考虑。
Say that an edge of a graphGdominates itself and every other edge sharing a vertex of it. An edge dominating set of a graphG= (V,E) is a subset of edgesE′ ⊆Ewhich dominates all edges ofG. In particular, if every edge ofGis dominated by exactly one edge ofE′ thenE′ is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighted dominating induced matching, if any, and counting the number of dominating induced matchings of a graph with weighted edges. We describe an exact algorithm for general graphs that runs inO*(1.1939n) time and polynomial (linear) space, for solving these problems. This improves over the existing exact algorithms for the problems in consideration.