TY  - JOUR
ID  - Ziemann2025
LB  - Ziemann2025
AU  - Ziemann, Radosław
AU  - Żyliński, Paweł
TI  - A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
ST  - A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2025
VL  - 45
IS  - 6
SP  - 841
EP  - 855
DO  - https://doi.org/10.7494/OpMath.2025.45.6.841
UR  - https://doi.org/10.7494/OpMath.2025.45.6.841
AB  - We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.
KW  - tree
KW  - domination
KW  - independence
KW  - vertex cover
KW  - dissociation
KW  - algorithm
KW  - linear time
KW  - dynamic programming
SN  - 1232-9274
ER  -