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 条

[21] A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
Panda, B. S.
Pradhan, D.
DISCRETE APPLIED MATHEMATICS, 2013, 161 (12) : 1776 - 1783
[22] AN O(EVLOGV) ALGORITHM FOR FINDING A MAXIMAL WEIGHTED MATCHING IN GENERAL GRAPHS
GALIL, Z
MICALI, S
GABOW, H
SIAM JOURNAL ON COMPUTING, 1986, 15 (01) : 120 - 130
[23] A linear time algorithm for the minimum Weighted Feedback Vertex Set on diamonds
Carrabs, F
Cerulli, R
Gentili, A
Parlato, G
INFORMATION PROCESSING LETTERS, 2005, 94 (01) : 29 - 35
[24] Breaking the O(ln n) Barrier: An F hanced Approximation Algorithm for Fault-Tolerant Minimum Weight connected Dominating Set
Zhou, Jiao
Zhang, Zhao
Tang, Shaojie
Huang, Xiaohui
Duc, Ding-Zhu
INFORMS JOURNAL ON COMPUTING, 2018, 30 (02) : 225 - 235
[25] A linear-time algorithm for minimum k-hop dominating set of a cactus graph
Abu-Affash, A. Karim
Carmi, Paz
Krasin, Adi
DISCRETE APPLIED MATHEMATICS, 2022, 320 : 488 - 499
[26] A generalized linear time algorithm for an optimal k-distance dominating set of a weighted tree
Kundu, Sukhamay
INFORMATION PROCESSING LETTERS, 2018, 130 : 58 - 62
[27] An O(n(m plus n log n) log n) time algorithm to solve the minimum cost tension problem
Ghiyasvand, Mehdi
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (03) : 957 - 969
[28] An O(n√n, log log n) average case algorithm for the maximum induced matching problem in permutation graphs
Viet Cuong Than
Phan Thuan Do
PROCEEDINGS OF THE 2018 5TH ASIAN CONFERENCE ON DEFENSE TECHNOLOGY (ACDT 2018), 2018, : 45 - 49
[29] Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm
Chuzhoy, Julia
Khanna, Sanjeev
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 83 - 94
[30] Matching nuts and bolts in O(n log n) time
Komlos, J
Ma, Y
Szemeredi, E
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 232 - 241

← 1 2 3 4 5 →