On the k-rainbow domination in graphs with bounded tree-width
| Main Authors: | Meybodi, M. Alambardar; Department of Applied Mathematics and Computer Science, Faculty of Mathematics and Statistics, University of Isfahan, Iran, Hooshmandasl, M. R.; Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran, Sharifani, P.; Institute for Research in Fundamental Sciences(IPM), Tehran, Iran, Shakiba, Ali; Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran. |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/615 https://www.ejgta.org/index.php/ejgta/article/view/615/pdf_179 |
Daftar Isi:
- Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪u ∈ N(v)f(u)=Ik where N(v) is the set of all neighbors of vertex v and Ik = {1, ..., k}. Finding a k-rainbow function of minimum weight of ∑v ∈ V|f(v)|, which is called the k-rainbow domination problem, is known to be NP-complete for arbitrary graphs and values of k. In this paper, we propose a dynamic programming algorithm to solve the k-rainbow domination problem for graphs with bounded tree-width tw in O((2k + 1+1)twn) time, where G has n vertices. Moreover, we also show that the same approach is applicable to solve the weighted k-rainbow domination problem with the same complexity. Therefore, both problems of k-rainbow and weighted k-rainbow domination belong to the class FPT, or fixed parameter tractable, with respect to tree-width. In addition to formally showing the correctness of our algorithms, we also implemented these algorithms to illustrate some examples.