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

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