Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
M. R. Hooshmandasl
Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
On the k-rainbow domination in graphs with bounded tree-width M. Alambardar Meybodi; M. R. Hooshmandasl; P. Sharifani; Ali Shakiba
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2021.9.2.4

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.
Co-Authors Ali Shakiba M. Alambardar Meybodi P. Sharifani