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

DOI10.1016/j.ipl.2015.07.014zbMath1346.05285OpenAlexW1149456426MaRDI QIDQ894482

Sukhamay Kundu, Subhashis Majumder

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.07.014

zbMATH Keywords

graph algorithmsrooted tree\(k\)-hop dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph, A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree, Relationship between optimal \(k\)-distance dominating sets in a weighted graph and its spanning trees, COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES, Unnamed Item, An optimal algorithm to find minimum k-hop dominating set of interval graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Algorithm and hardness results on hop domination in graphs

Cites Work

• A linear algorithm for the domination number of a tree
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• R -Domination in Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item