A linear time algorithm for optimal k-hop dominating set of a tree

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...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2016-02, Vol.116 (2), p.197-202
Main Authors: Kundu, Sukhamay, Majumder, Subhashis
Format: Article
Language:English
Subjects:
Algorithms
Graph algorithms
Information processing
k-Hop dominating set
Rooted tree
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2015.07.014