On linear programming relaxation for k-tuple domination number
سال انتشار: 1396
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 381
متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICIORS10_073
تاریخ نمایه سازی: 11 شهریور 1397
چکیده مقاله:
For a given graph G = (V,E) , it is proved that finding its domination number (G) and consequently k -tuple domonation number is an NP-complete problem. In this paper, first a linear integer programming model is presented to find the k -tuple dominating set. Then, the linear relaxation is applied to this integer programming model and an approximation of the k -tuple domonation number (G) k is obtained. Finaly, these relaxed and integer programming models are utilized to some special graphs and the numerical results are compared
کلیدواژه ها:
نویسندگان
Mehdi Djahangiri
Department of Mathematics, University of Maragheh
Shahram Morowati-Shalilvand
Department of Mathematics, University of Tabriz