Seminar za matematičku logiku i računarstvo

Na Seminaru za matematičku logiku i računarstvo, u ponedjeljak 21. srpnja 2025. u 17:15 sati, u predavaonici 201, PMF-MO, Noémie Catherinot (Ecole Normale Supérieure Paris-Saclay, Paris, France) održat će predavanje 

Edge-Cost Double Roman Domination

Sažetak: In this seminar, we will discuss an Edge-Cost variant of the Double Roman Domination problem. The Double Roman Domination problem is a domination and optimization problem on graphs, inspired by the defense strategies of the Roman Empire.

Intuitively, it aims to minimize the number of legions needed to secure the empire by allocating them to provinces such that, for each province, either it has enough legions to defend itself, or neighboring provinces can send legions without becoming defenseless themselves.

Formally, it involves assigning weights to vertices and minimizing the total number of units while satisfying a "security" condition.

However, the traditional Double Roman Domination problem only considers the number of legions allocated and does not account for the cost in resources or the time required for legions to travel to provinces in need of assistance.

We introduce the Edge-Cost variant of Double Roman Domination, which aims to minimize both the number of legions allocated and the cost of travel.