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

نوع مقاله : مقاله پژوهشی

نویسنده

دانشکده علوم ریاضی- دانشگاه صنعتی شاهرود- شاهرود- ایران

10.22034/csj.2023.184641

چکیده

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

کلیدواژه‌ها


[1]    Stewart, I., “Defend the Roman empire!”, Sci. Amer. 281 (1999) 136–139.
[2]    ReVelle, C.S., Rosing, K.E., “Defendens imperium romanum: a classical problem in military strategy”, Amer. Math. Monthly 107 (2000) 585–594.
[3]    Cockayne, E.J., Dreyer Sr., P.M., Hedetniemi, S.M., Hedetniemi, S.T., “Roman domination in graphs”, Discrete Math. 278 (2004) 11–22.
[4]    Beeler, R.A., Haynes, T.W., Hedetniemi, S.T., “Double Roman domination”, Discrete Appl. Math. 211 (2016) 23–29
[5]    Chellali, M., Haynes, T.W., Hedetniemi, S.T., MacRae, A., “Roman {2}-domination”, Discrete Appl. Math. 204 (2016) 22–28.
[6]    Abdollahzadeh Ahangar, H., Henning, M.A., Samodivkin, V., Yero, I.G., “Total Roman domination in graphs”, Applicable Analysis and Discrete Mathematics, 10 (2016) 501-517.
[7]    Abdollahzadeh Ahangar, H., Henning, M.A., Löwenstein, C., Zhao, Y., Samodivkin, V., “Signed Roman domination in graphs”, Journal of Combinatorial Optimization, 27 (2014) 241-255.
[8]    Roushini Leely Pushpam, P., Padmapriea, S., “Global Roman domination in graphs”, Discrete Appl. Math. 200 (2016) 176–185.
[9]    Chellali, M., Jafari Rad, N., Sheikholeslami, S.M., Volkmann, L., “Varieties of Roman domination II”, AKCE International Journal of Graphs and Combinatorics, 17 (2020) 966-984.
[10]  Henning, M.A., Klostermeyer, W.F., “Italian domination in trees”, Discrete Appl. Math. 217 (2017) 557–564.
[11]  Poureidi, A., Jafari Rad, N., “On the algorithmic complexity of Roman {2}-domination (Italian domination)”, Iran J. Sci. Technol. Trans. Sci. 44 (2020) 791–799.
[12]  Padamutham, C., Palagiri , V. S. R., “Complexity of Roman {2}-domination and the double Roman domination in graphs”, AKCE Int. J. Graphs and Combin., 17 (2020) 1081–1086.
[13]  Vazirani., V., “Approximation Algorithms” Springer-Verlag, Berlin, Germany, 2001.
[14]  Hromkovic, J., “Algorithms for Hard Problems” Springer-Verlag Berlin Heidlberg, 2001.
[15]  Dobson, G., “Worst-case analysis of greedy heuristics for integer programming with nonnegative data”, Math. Oper. Res 7 (1982) 515–531.