A linear time algorithm for optimal k -hop dominating set of a tree
| Autor: | Sukhamay Kundu, Subhashis Majumder |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
K-ary tree 010103 numerical & computational mathematics 0102 computer and information sciences 01 natural sciences Connected dominating set Computer Science Applications Theoretical Computer Science Hop (networking) Combinatorics Tree (data structure) 010201 computation theory & mathematics Dominating set Signal Processing Graph algorithms 0101 mathematics Time complexity Algorithm Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 116:197-202 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2015.07.014 |
| Popis: | We give a linear time algorithm to compute an optimal (minimum) k-hop dominating set D of a tree T for k ? 1 . This extends the previous result for an optimal 1-dominating set for trees. We use a rooted form T ? of T, with an arbitrary node selected as the root, to direct the search for nodes of D in a bottom-up fashion. The decision whether to include a node x in D or not is based on the subtree of T ? at x. Optimal k-hop dominating sets have many important practical applications. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect