Exact Algorithms for Minimum Weighted Dominating Induced Matching

详细信息    查看全文

• 作者：Min Chih Lin ; Michel J. Mizrahi ; Jayme L. Szwarcfiter
• 关键词：Exact algorithms ; Graph theory ; Dominating induced matchings
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：77
• 期：3
• 页码：642-660
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

Say that an edge of a graph G dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph \(G=(V,E)\) is a subset of edges \(E' \subseteq E\) which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of \(E'\) then \(E'\) 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 counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an \(O^*(1.1939^n)\) time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs.