A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
Loading...
Date
Presentation Date
Editor
Authors
Other contributors
Other title
Resource type
Version
wersja wydawnicza
Pagination/Pages:
pp. 841-855
Research Project
Description
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.