[Home ] [Archive]    
:: Main :: About :: Current Issue :: Archive :: Search :: Submit :: Registration ::
Main Menu
Home::
Journal Information::
Articles archive::
Submission Instruction::
Registration::
Submit article::
Site Facilities::
Contact us::
::
Google Scholar

Citation Indices from GS

AllSince 2019
Citations85403575
h-index127
i10-index136

Search in website

Advanced Search
Receive site information
Enter your Email in the following box to receive the site news and information.
:: 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:   (11007 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]   (16653 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:

CAPTCHA


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.07 seconds with 39 queries by YEKTAWEB 4645