Improved Mixed Integer Linear Programing Formulations for Roman Domination Problem

Marija Ivanović

The Roman domination problem is considered. An improvement of two existing Integer Linear Programing (ILP) formulations is proposed and comparison between the old and new ones is given. Correctness proofs show that improved linear programing formulations are equivalent to the existing ones regardless of the variables relaxation and usage of lesser number of constraints.