科研之友
微信
新浪微博
Facebook
分享链接
摘要
Alber et al. presented an algorithm for computing a dominating set of size at most k, if one exists, in an undirected planar n-vertex graph and bounded its execution time by O(8(k)0). Here it is shown that the algorithm performs better than claimed by its authors. More significantly, if k %26lt;= n/19, even a much simplified version of the algorithm runs in O(7(k)n) time.
- 出版日期2012-4
