یک الگوریتم تقریبی برای حل مسئله تابع احاطه گر ایتالیایی روی گراف ها
محل انتشار: مجله علوم رایانشی، دوره: 8، شماره: 3
سال انتشار: 1402
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 66
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_CSJI-8-3_006
تاریخ نمایه سازی: 14 بهمن 1402
چکیده مقاله:
گراف G=(V,E) را در نظر بگیرید. تابع f:V→{۰,۱,۲} را یک تابع احاطه گر ایتالیایی (احاطه گر {۲}- رومن) گویند هرگاه هر راس v∈V با f(v)=۰ مجاور به حداقل یک راس u∈V با f(u)=۲ یا مجاور به حداقل دو راس x,y∈V با f(x)=f(y)=۱ باشد. وزن یک تابع احاطه گر ایتالیایی برای گراف G با کمترین مقدار را عدد احاطه گر ایتالیایی گراف G گوییم. مسئله تابع احاطه گر ایتالیایی برای گراف G به صورت یافتن یک تابع احاطه گر ایتالیایی با وزن برابر با عدد احاطه گر ایتالیایی برای گراف G تعریف می شود. ثابت شده است که مسئله تابع احاطه گر ایتالیایی NP-کامل است. در این مقاله ابتدا یک مدل برنامه ریزی خطی صحیح برای این مسئله پیشنهاد می کنیم و سپس با استفاده از این مدل یک الگوریتم تقریبی با ضریب H(۲∆(G)+۲) برای حل مسئله ارائه می کنیم.
کلیدواژه ها:
نویسندگان
ابوالفضل پورعیدی
دانشکده علوم ریاضی- دانشگاه صنعتی شاهرود- شاهرود- ایران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :