Semidefinite relaxation for dominating set
|
Alireza Ghaffari-Hadigheh Dr, Mehdi Djahangiri |
Azarbaijan Shahid Madani University , djahangiri.mehdi@azaruniv.edu |
|
Abstract: (5458 Views) |
It is a well-known fact that finding a minimum dominating set and consequently the domination number of a general graph is an NP-complete problem. In this paper, we first model it as a nonlinear binary optimization problem and then extract two closely related semidefinite relaxations. For each of these relaxations, different rounding algorithm is exploited to produce a near-optimal dominating set. Feasibility of the generated solutions and efficiency of the algorithms are analyzed as well. |
|
Keywords: Dominating Set, SemiDefinite Programming, Rounding Algorithm. |
|
Full-Text [PDF 426 kb]
(3705 Downloads)
|
Type of Study: Original |
Subject:
Continuous Optimization Received: 2015/05/26 | Accepted: 2016/02/18 | Published: 2017/03/27
|
|
|
|