Iranian Journal of Operations Research
مجله انجمن ایرانی تحقیق در عملیات
IJOR
Basic Sciences
http://iors.ir/journal
0
user
2008-1189
10.29252/iors
en
jalali
1393
12
1
gregorian
2015
3
1
6
1
online
1
fulltext
en
Semidefinite relaxation for dominating set
Continuous Optimization
Continuous Optimization
پژوهشی
Original
<p>‎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‎.</p>
Dominating Set, SemiDefinite Programming, Rounding Algorithm.
53
64
http://iors.ir/journal/browse.php?a_code=A-10-667-1&slc_lang=en&sid=1
Alireza
Ghaffari-Hadigheh
علیرضا
غفاری حدیقه
hadigheha@azaruniv.edu
00031947532846001452
00031947532846001452
No
Azarbaijan Shahid Madani University
دانشگاه شهید مدنی آذربایجان
Mehdi
Djahangiri
djahangiri.mehdi@azaruniv.edu
00031947532846001453
00031947532846001453
Yes
Azarbaijan Shahid Madani University
دانشگاه شهید مدنی آذربایجان