Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
3-Rainbow Domination Number in Graphs
verfasst von : Kung-Jui Pai, Wei-Jai Chiu
Erschienen in: Proceedings of the Institute of Industrial Engineers Asian Conference 2013
Verlag: Springer Singapore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The k-rainbow domination is a location problem in operations research. Give an undirected graph G as the natural model of location problem. We have a set of k colors and assign an arbitrary subset of these colors to each vertex of G. If a vertex which is assigned an empty set, then the union of color set of its neighbors must be k colors. This assignment is called the k-rainbow dominating function, abbreviate as kRDF, of G. The weight of kRDF is the sum of numbers of assigned colors over all vertices of G. The minimum weight of kRDF is defined as the k-rainbow domination number of G. In this paper, we present an exact algorithm and a heuristic algorithm to obtain the 3-rainbow domination number and the weight of 3RDF in graphs, respectively. Then, we test the practical performances of these algorithms, including their run times and solution qualities.