@Article{Ziemann2025,
author = "Ziemann, Radosław and Żyliński, Paweł",
title = "A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences",
journal = "Opuscula Math.",
year = "2025",
volume = "45",
number = "6",
pages = "841--855",
doi = "https://doi.org/10.7494/OpMath.2025.45.6.841",
url = "https://doi.org/10.7494/OpMath.2025.45.6.841",
abstract = "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.",
keywords = "tree, domination, independence, vertex cover, dissociation, algorithm, linear time, dynamic programming",
issn = "1232-9274"
}