فهرست نشریات علمی دسترسی آزاد ایران

گراف G=(V,E) را در نظر بگیرید. تابع f:V→{0,1,2} را یک تابع احاطه‌گر ایتالیایی (احاطه‌گر {2}- رومن) گویند هرگاه هر راس v∈V با f(v)=0 مجاور به حداقل یک راس u∈V با f(u)=2 یا مجاور به حداقل دو راس x,y∈V با f(x)=f(y)=1 باشد. وزن یک تابع احاطه‌گر ایتالیایی برای گراف G با کمترین مقدار را عدد احاطه‌گر  ایتالیایی گراف G گوییم. مسئله تابع احاطه‌گر ایتالیایی برای گراف G به صورت یافتن یک تابع احاطه‌گر ایتالیایی با وزن برابر با عدد احاطه‌گر ایتالیایی برای گراف G تعریف می‌شود. ثابت شده است که مسئله تابع احاطه‌گر ایتالیایی NP-کامل است. در این مقاله ابتدا یک مدل برنامه‌ریزی خطی صحیح برای این مسئله پیشنهاد می‌کنیم و سپس با استفاده از این مدل یک الگوریتم تقریبی با ضریب H(2∆(G)+2) برای حل مسئله ارائه می‌کنیم.