یک الگوریتم تقریبی برای حل مسئله تابع احاطه‌گر ایتالیایی روی گراف‌ها

گراف 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) برای حل مسئله ارائه می‌کنیم.