A generalized linear time algorithm for an optimal k-distance dominating set of a weighted tree

The new algorithm finds an optimal k-distance dominating set D in a weighted trees T=(V,E) with link-weights w(x,y)>0 in time O(|V|). It generalizes a previous linear time algorithm for an optimal k-hop dominating set for an unweighted tree. This significantly increases the applications of domina...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2018-02, Vol.130, p.58-62
Main Author: Kundu, Sukhamay
Format: Article
Language:English
Subjects:
Algorithms
k-distance dominating set
Weighted tree
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The new algorithm finds an optimal k-distance dominating set D in a weighted trees T=(V,E) with link-weights w(x,y)>0 in time O(|V|). It generalizes a previous linear time algorithm for an optimal k-hop dominating set for an unweighted tree. This significantly increases the applications of dominating sets in trees. •It generalizes a linear time algorithm for a k-hop optimal dominating set of an unweighted tree to a weighted tree.•This significantly increases the applications of dominating sets in real life problems.•The algorithm determines an optimal k-distance dominating set by selecting one node at a time in a bottom–up fashion.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2017.10.009