:: Volume 6, Issue 1 (3-2015) ::
IJOR 2015, 6(1): 53-64 Back to browse issues page
Semidefinite relaxation for dominating set
Alireza Ghaffari-Hadigheh , Mehdi Djahangiri *
Azarbaijan Shahid Madani University , djahangiri.mehdi@azaruniv.edu
Abstract:   (12145 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]   (20084 Downloads)    
Type of Study: Original | Subject: Continuous Optimization
Received: 2015/05/26 | Accepted: 2016/02/18 | Published: 2017/03/27


XML     Print



Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Volume 6, Issue 1 (3-2015) Back to browse issues page