A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
Opuscula Mathematica · 2025 · 841-855
DOI: 10.7494/opmath.2025.45.6.841 ↗Kurz gefasst
Fachartikel in der Zeitschrift Opuscula Mathematica, 2025. Verfasst von Radosław Ziemann und 1 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Ziemann, R., & Żyliński, P. (2025). A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences. Opuscula Mathematica, 841-855. https://doi.org/10.7494/opmath.2025.45.6.841
Vancouver
Ziemann R, Żyliński P. A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences. Opuscula Mathematica. 2025:841-855. doi:10.7494/opmath.2025.45.6.841
BibTeX
@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 Mathematica},
year = {2025},
pages = {841--855},
doi = {10.7494/opmath.2025.45.6.841}
}
EUVIMED