EMIS ELibM Electronic Journals Publications de l'Institut Mathématique, Nouvelle Série
Vol. 99(113), pp. 51–58 (2016)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

Pick a mirror

 		 

IMPROVED MIXED INTEGER LINEAR PROGRAMING FORMULATIONS FOR ROMAN DOMINATION PROBLEM

Marija Ivanovic

Faculty of Mathematics, Department for Applied Mathematics, University of Belgrade, Belgrade, Serbia

Abstract: 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.

Keywords: Roman domination in graphs; combinatorial optimization; mixed integer linear programming

Classification (MSC2000): 65K05; 90C11; 90C05; 94C15; 68R10

Full text of the article: (for faster download, first choose a mirror)

Electronic fulltext finalized on: 12 Apr 2016. This page was last modified: 20 Apr 2016.

© 2016 Mathematical Institute of the Serbian Academy of Science and Arts
© 2016 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition