A linear time algorithm for optimal k-hop dominating set of a tree
DOI10.1016/J.IPL.2015.07.014zbMATH Open1346.05285OpenAlexW1149456426MaRDI QIDQ894482FDOQ894482
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Title not available (Why is that?)
- A linear algorithm for the domination number of a tree
- Algorithmic aspects of the \(k\)-domination problem in graphs
- Title not available (Why is that?)
- R -Domination in Graphs
Cited In (12)
- Title not available (Why is that?)
- Algorithm and hardness results on hop domination in graphs
- 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
- 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
- Title not available (Why is that?)
- A linear‐time algorithm for broadcast domination in a tree
- A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
- COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES
- Guarding polyominoes under \(k\)-hop visibility
- Edge-vertex domination on interval 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)
