Browsing by Subject "linear time"
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Item type:Article, Access status: Open Access , A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences(Wydawnictwa AGH, 2025) Ziemann, Radosław; Żyliński, Paweł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.