TY - JOUR ID - 76537 TI - On computing total double Roman domination number of trees in linear time JO - Journal of Algorithms and Computation JA - JAC LA - en SN - 2476-2776 AU - Poureidi, Abolfazl AD - Department of Mathematics, Shahrood University of Technology Shahrood, Iran Y1 - 2020 PY - 2020 VL - 52 IS - 1 SP - 131 EP - 137 KW - Total double Roman dominating function KW - linear algorithm KW - Dynamic Programming KW - Combinatorial optimization KW - tree DO - 10.22059/jac.2020.76537 N2 - Let $G=(V,E)$ be a graph. A doubleRoman dominating function (DRDF) on $G$ is a function$f:V\to\{0,1,2,3\}$ such that for every vertex $v\in V$if $f(v)=0$, then either there is a vertex $u$ adjacent to $v$ with $f(u)=3$ orthere are vertices $x$ and $y$ adjacent to $v$ with $f(x)=f(y)=2$ and if $f(v)=1$, then there is a vertex $u$ adjacent to $v$ with$f(u)\geq2$.A DRDF $f$ on $G$ is a total DRDF (TDRDF) if for any $v\in V$ with $f(v)>0$ there is a vertex $u$ adjacent to $v$ with $f(u)>0$.The weight of $f$ is the sum $f(V)=\sum_{v\in V}f(v)$. The minimum weight of a TDRDF on $G$ is the total double Romandomination number of $G$. In this paper, we give a linear algorithm to compute thetotal double Roman domination number of agiven tree. UR - https://jac.ut.ac.ir/article_76537.html L1 - https://jac.ut.ac.ir/article_76537_69021667b614187aa822b65828743678.pdf ER -