[Home ] [Archive]    
:: Main :: About :: Current Issue :: Archive :: Search :: Submit :: Registration ::
:: 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:   (7900 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]   (8065 Downloads)    
Type of Study: Original | Subject: Continuous Optimization
Received: 2015/05/26 | Accepted: 2016/02/18 | Published: 2017/03/27
Send email to the article author

Add your comments about this article
Your username or Email:


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
مجله انجمن ایرانی تحقیق در عملیات Iranian Journal of Operations Research
Persian site map - English site map - Created in 0.04 seconds with 30 queries by YEKTAWEB 4414