Title :
A mathematical model for finding the rainbow connection number
Author :
Nuriyeva, Fidan ; Ugurlu, Onur ; Kutucu, Hakan
Author_Institution :
Dept. of Math., Ege Univ., Izmir, Turkey
Abstract :
The rainbow connection problem belongs to the class of NP-Hard graph theoretical problems. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow edge-connected. In this study, we present a new mathematical model for the rainbow connection problem.
Keywords :
computational complexity; graph colouring; number theory; set theory; NP-hard graph theoretical problems; connected graph; edge coloring; edge set; finite graph; mathematical model; rainbow connection number; rainbow connectivity; simple graph; undirected graph; Approximation algorithms; Color; Complexity theory; Educational institutions; Heuristic algorithms; Mathematical model; Rainbow connection; mathematical modelling; optimization;
Conference_Titel :
Application of Information and Communication Technologies (AICT), 2013 7th International Conference on
Conference_Location :
Baku
Print_ISBN :
978-1-4673-6419-5
DOI :
10.1109/ICAICT.2013.6722630
