Greedy approximation for the minimum connected dominating set with labeling

DOI10.1007/s11590-020-01628-6zbMath1466.90092OpenAlexW3048387367MaRDI QIDQ828691

Majun Shi, Zishen Yang, 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

labelingapproximation algorithmgreedy algorithmconnected dominating setperformance ratio

Mathematics Subject Classification ID

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

Related Items (3)

A unified greedy approximation for several dominating set problems ⋮ Minimum non-submodular cover problem with applications ⋮ Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem

Cites Work

• Connected dominating set. Theory and applications
• Design and analysis of approximation algorithms
• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for connected dominating sets
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• A note on the minimum label spanning tree.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• A threshold of ln n for approximating set cover
• On colouring random graphs
• Spanning trees with many or few colors in edge-colored graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

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