Greedy approximation for the minimum connected dominating set with labeling

DOI10.1007/S11590-020-01628-6MaRDI QIDQ828691zbMATH OpenOpenAlexFDO

Authors Zishen Yang, Majun Shi, Wei Wang

Publication date 5 May 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-020-01628-6

zbMATH Keywords

approximation algorithmconnected dominating setgreedy algorithmlabelingperformance ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for connected dominating sets
• A unified greedy approximation for several dominating set problems
• Approximation algorithms for connected dominating sets
• A greedy approximation for minimum connected dominating sets
• Minimum connected dominating sets in finite graphs

Cites work

• A greedy approximation for minimum connected dominating sets
• A note on the minimum label spanning tree.
• A threshold of ln n for approximating set cover
• Approximation algorithms for connected dominating sets
• Connected dominating set. Theory and applications
• Design and analysis of approximation algorithms
• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• scientific article; zbMATH DE number 3702724 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On colouring random graphs
• On the minimum label spanning tree problem
• Spanning trees with many or few colors in edge-colored graphs
• The minimum labeling spanning trees
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem

Cited in

(5)

• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
• Minimum non-submodular cover problem with applications
• A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
• A unified greedy approximation for several dominating set problems
• Minimum connected dominating sets in finite graphs

This page was built for publication: Greedy approximation for the minimum connected dominating set with labeling

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