FINDING MINIMUM AND MAXIMUM PAIRED ROMAN DOMINATIONS IN GRAPHS USING GREEDY AND LOCAL SEARCH ALGORITHMS

Abstract

Let G=(V,E) is a Roman domination function of a graph and the graph function is defined function f : V→{0,1,2} agreeing the condition that every vertex a for which f(a)=0 is adjacent to at least one vertex b for which f(b)=2. The minimum paired Roman domination number abbreviated as γ(G) is the minimum domination of Paired roman domination in a graph.The maximum paired Roman domination number, abbreviated as γp(G), is the highest possible cardinality for a pair of Roman dominating sets. In this paper, we propose greedy and local search algorithms for finding minimum and maximum paired Roman dominations in graphs. Our algorithms are based on the following observations: The greedy algorithm is more likely to find a minimum or maximum cardinality paired Roman dominating set if it starts with a good initial set S, The degree of a vertex is a good measure of its importance in a graph. The local search algorithm is used to improve the solution. The results of our experiments show that our algorithms outperform the greedy algorithm and the local search algorithm for finding minimum paired Roman dominations