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

DOI10.1016/J.IPL.2015.07.014MaRDI QIDQ894482zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree
• scientific article; zbMATH DE number 3959487
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• A linear‐time algorithm for broadcast domination in a tree
• A linear algorithm for \(\langle r, s \rangle\)-domination of a tree
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Approximating \(k\)-hop minimum-spanning trees
• A linear time algorithm for minimum equitable dominating set in trees
• Linear algorithms for edge-vertex domination in trees
• An optimal algorithm to find minimum \(k\)-hop dominating set of interval graphs

Cites work

• scientific article; zbMATH DE number 146666 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• R -Domination in Graphs
• 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

Cited in

(12)

• Algorithm and hardness results on hop domination in graphs
• Computational methods for logistics problems related to optimal trees
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• On the \(k\)-hop domination numbers of spanning trees of unicyclic graphs
• Relationship between optimal \(k\)-distance dominating sets in a weighted graph and its spanning trees
• A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree
• scientific article; zbMATH DE number 3959487 (Why is no real title available?)
• A linear‐time algorithm for broadcast domination in a tree
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• Guarding polyominoes under \(k\)-hop visibility
• Edge-vertex domination on interval graphs
• An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs

This page was built for publication: A linear time algorithm for optimal \(k\)-hop dominating set of a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894482)