ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION
عنوان مقاله: ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION
شناسه ملی مقاله: JR_JAS-10-2_001
منتشر شده در در سال 1402
شناسه ملی مقاله: JR_JAS-10-2_001
منتشر شده در در سال 1402
مشخصات نویسندگان مقاله:
S.H. Mirhoseini - Department of Mathematics, Shahed University, Tehran, Iran.
N. Jafari Rad - Department of Mathematics, Shahed University, Tehran, Iran.
خلاصه مقاله:
S.H. Mirhoseini - Department of Mathematics, Shahed University, Tehran, Iran.
N. Jafari Rad - Department of Mathematics, Shahed University, Tehran, Iran.
A perfect Roman dominating function (PRDF) on a graph G is a function f:V(G)\to \{۰,۱,۲\} satisfying the condition that every vertex u with f(u) = ۰ is adjacent to exactly one vertex v for which f(v) = ۲. The weight of a PRDF f is the sum of the weights of the vertices under f. The perfect Roman domination number of G is the minimum weight of a PRDF in G. In this paper we study algorithmic and computational complexity aspects of the minimum perfect Roman domination problem (MPRDP). We first correct the proof of a result published in [BulletinIran. Math. Soc. ۱۴(۲۰۲۰), ۳۴۲--۳۵۱], and using a similar argument, show that MPRDP is APX-hard for graphs with bounded degree ۴.We prove that the decision problem associated to MPRDP is NP-complete even when restricted to star convex bipartite graphs. Moreover, we show that MPRDP is solvable in linear time for bounded tree-widthgraphs. We also show that the perfect domination problem and perfect Roman domination problem are not equivalent in computational complexity aspects. Finally we propose an integer linear programming formulation for MPRDP.
کلمات کلیدی: Dominating set, perfect dominating set, Roman dominating function, perfect Roman dominating function, APX-hard
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/1489975/