Roman Domination

A subset of dominating set Problems

a strategy of Emperor Constantine for defending the Roman Empire.

Roman dominating function is a colouring of the vertices of a graph with the colours {0; 1; 2} such that every vertex coloured 0 is adjacent to at least one vertex coloured 2

An interesting variety of domination that is popular because of its historical signifi cance is called Roman domination. In the 4th century Emperor Constantine, in order to defend the Roman Empire, decreed that two types of armies should be placed in cities in such a way that the entire Empire could be secured. The first type of army was highly trained and mobile, and could move from city to city to defend against any attack. The second type of army was a local militia that was permanently stationed at a given city. The Emperor decreed that no mobile army could ever leave a city to defend another if in doing so it left the originating city undefended. Thus, two armies were stationed at some cities, only a local militia at others, and other cities had no army.

Problem Statement

Given a graph, a Roman Dominating Function is a function that labels the vertices of the graph with an integer between 0,1,2, satisfying the condition that every vertex labeled by 0 is adjacent to at least one vertex labeled by 2. The weight of a Roman Dominating Function is the sum of all the labels, and the minimum weight is called the Roman Domination Number. The Roman Domination Problem is to find such number and function

Variants

Resources

PhD Thesis

Curro Et Al 2014

Nolassi et al 2013

Topic: The Roman Domination Problem on Grid Graphs.

Datasets

grid, random, bipartite, net, planer, and recursive

Graph Data

Meta Heuristics Solutions

greihuber et. al. 23

Algorithm Explanation

#claude
The pseudocode takes a graph G = (V, E) as input, where V is the set of vertices, and E is the set of edges.

First, it initializes two variables du(v) and d2u(v) for each vertex v in the graph. du(v) represents the number of undominated neighbors of vertex v, and d2u(v) represents the number of vertices at distance exactly 2 from vertex v. These variables will be used as heuristics to guide the selection of vertices.

The code then initializes an array f of the same size as V, where f(v) represents the status of vertex v. Initially, all vertices are marked as "unlabeled" (f(v) = unlabeled).

The algorithm then enters a loop that iterates until there is no vertex in S (initially set to V) with two or more undominated neighbors (du(v) >= 2). In each iteration, it selects the vertex v from S with the largest du value. If the tiebreaker option is enabled, it prefers vertices with lower d2u values in case of ties.

For the selected vertex v, it sets f(v) to 2 (representing a dominating vertex) and marks all its unlabeled neighbors as dominated by setting f(n) to 0 for all n in N(v), the set of neighbors of v.

After the loop terminates, all remaining unlabeled vertices are labeled with 1 (representing dominated vertices).

The code then performs a post-processing step, which is a local improvement step. It iterates over all vertices v with f(v) = 2 (dominating vertices). For each such vertex v, it temporarily sets f(v) to 0 (non-dominating) and checks if the Roman Domination condition is violated for any neighbor u of v. If the condition is violated for any neighbor, it reverts f(v) back to 2 (dominating). If the condition is not violated for any neighbor but is violated for v itself, it sets f(v) to 1 (dominated).

Finally, the algorithm returns the updated f array, which represents the Roman Dominating Function (RDF) for the input graph.

The pseudocode uses a greedy approach to select dominating vertices based on the du and d2u heuristics, followed by a local improvement step to refine the solution. However, it's important to note that this is not the typical simulated annealing algorithm, as it does not incorporate the core aspects of simulated annealing, such as a cooling schedule, acceptance probability, and stochastic perturbations.

Domination Number

Github Repos

Cockayne et al. [4] introduce the term Roman domination

such as the observation that the Roman domination number is at least the size of the domination number (i.e., the cardinality of the smallest dominating set) and at most twice this number for any graph.

Other PhD thesis regarding RDP in GRID graph

Enter your search text in the box above

Select a result to preview