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

DOI10.1016/J.IPL.2017.10.009MaRDI QIDQ1679914zbMATH OpenOpenAlexFDO

Authors Sukhamay Kundu

Publication date 22 November 2017

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

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

zbMATH Keywords

\(k\)-distance dominating setalgorithmsweighted tree

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A linear time algorithm for optimal \(k\)-hop dominating set of a tree
• scientific article; zbMATH DE number 5732600
• Relationship between optimal \(k\)-distance dominating sets in a weighted graph and its spanning trees
• A distributed algorithm for minimum distance-k domination in trees
• scientific article; zbMATH DE number 3959487

Cites work

• R -Domination in Graphs
• A linear algorithm for the domination number of a tree
• A linear time algorithm for optimal \(k\)-hop dominating set 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
• 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?)

Cited in

(5)

• An optimal time algorithm for finding a maximum weight independent set in a tree
• Relationship between optimal \(k\)-distance dominating sets in a weighted graph and its spanning trees
• scientific article; zbMATH DE number 5732600 (Why is no real title available?)
• A distributed algorithm for minimum distance-k domination in trees
• A linear time algorithm for optimal \(k\)-hop dominating set of a tree

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

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