Back to Search
Start Over
On the k-rainbow domination in graphs with bounded tree-width
- Source :
- Electronic Journal of Graph Theory and Applications, Vol 9, Iss 2, Pp 277-300 (2021)
- Publication Year :
- 2021
- Publisher :
- The Institute for Research and Community Services (LPPM) ITB, 2021.
-
Abstract
- 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 𝒪((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.
- Subjects :
- Applied Mathematics
Minimum weight
Rainbow
Function (mathematics)
Power set
Combinatorics
Treewidth
Bounded function
QA1-939
Computer Science::Programming Languages
Discrete Mathematics and Combinatorics
Mathematics
domination, k-rainbow domination, weighted k-rainbow domination, bounded tree-width graphs
Subjects
Details
- ISSN :
- 23382287
- Volume :
- 9
- Database :
- OpenAIRE
- Journal :
- Electronic Journal of Graph Theory and Applications
- Accession number :
- edsair.doi.dedup.....a6272aa84d899293e86cbfd8374c2cf1