An O*(1.1939n) Time Algorithm for Minimum Weighted Dominating Induced Matching

被引：0

作者：

Min Chih Lin ^{[1
]}

Mizrahi, Michel J. ^{[1
]}

Szwarcfiter, Jayme L. ^{[2
]}

机构：

[1] Univ Buenos Aires, CONICET, Inst Calculo, Buenos Aires, DF, Argentina

[2] Univ Fed Rio de Janeiro, COPPE, NCE, BR-21945 Rio De Janeiro, Brazil

来源：

ALGORITHMS AND COMPUTATION | 2013年 / 8283卷

关键词：

exact algorithms; dominating induced matchings; branch & reduce; EFFICIENT EDGE DOMINATION; GRAPHS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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' subset of 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 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 in O*(1.1939(n)) time and polynomial (linear) space, for solving these problems. This improves over the existing exact algorithms for the problems in consideration.

引用

页码：558 / 567

页数：10

共 50 条

[1] Exact Algorithms for Minimum Weighted Dominating Induced Matching
Min Chih Lin
Michel J. Mizrahi
Jayme L. Szwarcfiter
Algorithmica, 2017, 77 : 642 - 660
[2] Exact Algorithms for Minimum Weighted Dominating Induced Matching
Lin, Min Chih
Mizrahi, Michel J.
Szwarcfiter, Jayme L.
ALGORITHMICA, 2017, 77 (03) : 642 - 660
[3] O(n) Time Algorithms for Dominating Induced Matching Problems
Lin, Min Chih
Mizrahi, Michel J.
Szwarcfiter, Jayme L.
LATIN 2014: THEORETICAL INFORMATICS, 2014, 8392 : 399 - 408
[4] An O(n plus m) time algorithm for computing a minimum semitotal dominating set in an interval graph
Pradhan, D.
Pal, Saikat
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2021, 66 (1-2) : 733 - 747
[5] An O(n+m)-time algorithm for finding a minimum-weight dominating set in a permutation graph
Rhee, C
Liang, YD
Dhall, SK
Lakshmivarahan, S
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) : 404 - 419
[6] A PARTITIONING ALGORITHM FOR MINIMUM WEIGHTED EUCLIDEAN MATCHING
DYER, ME
FRIEZE, AM
INFORMATION PROCESSING LETTERS, 1984, 18 (02) : 59 - 62
[7] An o*(1.4786n)-time algorithm for the maximum induced matching problem
1600, Springer Science and Business Media Deutschland GmbH (20):
[8] AN O(N) TIME ALGORITHM FOR MAXIMUM MATCHING ON COGRAPHS
YU, MS
YANG, CH
INFORMATION PROCESSING LETTERS, 1993, 47 (02) : 89 - 93
[9] A 5+ε-approximation algorithm for minimum weighted dominating set in unit disk graph
Dai, Decheng
Yu, Changyuan
THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) : 756 - 765
[10] An O(N2) Algorithm for Computation of the Minimum Time Consensus
Mulla, Ameer K.
Patil, Deepak U.
Chakraborty, Debraj
2016 IEEE 55TH CONFERENCE ON DECISION AND CONTROL (CDC), 2016, : 2638 - 2643

← 1 2 3 4 5 →