An approximation algorithm for the prize-collecting connected dominating set problem

DOI10.1007/S11590-024-02160-7MaRDI QIDQ6893388zbMATH OpenFDO

Authors Yaoyao Zhang, Zhao Zhang, Du Ding-Zhu

Publication date 26 November 2025

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S11590-024-02160-7

zbMATH Keywords

approximation ratioconnected dominating setpenalty

Mathematics Subject Classification ID

Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A greedy approximation for minimum connected dominating sets
• An LMP O( n)-approximation algorithm for node weighted prize collecting Steiner tree
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• Approximation algorithms for connected dominating sets
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Design and analysis of approximation algorithms
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.

This page was built for publication: An approximation algorithm for the prize-collecting connected dominating set problem

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