On greedy approximation algorithm for the minimum resolving dominating set problem

DOI10.1007/S10878-024-01229-4MaRDI QIDQ7031280zbMATH OpenFDO

Authors Hao Zhong

Publication date 6 February 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-024-01229-4

zbMATH Keywords

greedy approximation algorithmNP-hardnessresolving dominating setsubmodular function

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation complexity of metric dimension problem
• Greedy approximations for minimum submodular cover with submodular cost
• Landmarks in graphs
• On approximation algorithm for the edge metric dimension problem

This page was built for publication: On greedy approximation algorithm for the minimum resolving dominating set problem

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