[صفحه اصلی ]   [Archive]  
:: صفحه اصلي :: درباره نشريه :: آخرين شماره :: تمام شماره‌ها :: جستجو :: ثبت نام :: ارسال مقاله :: تماس با ما ::
:: جلد 6، شماره 1 - ( 12-1393 ) ::
جلد 6 شماره 1 صفحات 53-64 برگشت به فهرست نسخه ها
Semidefinite relaxation for dominating set
دکتر علیرضا غفاری حدیقه
چکیده:   (4723 مشاهده)

‎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‎.

متن کامل [PDF 426 kb]   (2976 دریافت)    
نوع مطالعه: پژوهشی | موضوع مقاله: Continuous Optimization
دریافت: 1394/3/5 | پذیرش: 1394/11/29 | انتشار: 1396/1/7
ارسال نظر درباره این مقاله
نام کاربری یا پست الکترونیک شما:

CAPTCHA


XML   English Abstract   Print



جلد 6، شماره 1 - ( 12-1393 ) برگشت به فهرست نسخه ها
مجله انجمن ایرانی تحقیق در عملیات Iranian Journal of Operations Research
Persian site map - English site map - Created in 0.05 seconds with 30 queries by YEKTAWEB 4227