| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420186 | Discrete Applied Mathematics | 2012 | 6 Pages |
Abstract
Alber et al. presented an algorithm for computing a dominating set of size at most kk, if one exists, in an undirected planar nn-vertex graph and bounded its execution time by O(8kn)O(8kn). Here it is shown that the algorithm performs better than claimed by its authors. More significantly, if k≤n/19k≤n/19, even a much simplified version of the algorithm runs in O(7kn)O(7kn) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Torben Hagerup,