A unified greedy approximation for several dominating set problems

DOI10.1016/J.TCS.2023.114069MaRDI QIDQ6093579zbMATH OpenOpenAlexFDO

Authors

Publication date 7 September 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114069

zbMATH Keywords

approximation algorithmdominating setsubmodularityconnected dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for connected dominating sets
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Approximation algorithms for connected dominating sets
• Minimum connected dominating sets in finite graphs

Cites work

• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks
• A greedy approximation for minimum connected dominating sets
• An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks
• An analysis of the greedy algorithm for the submodular set covering problem
• Greedy approximation for the minimum connected dominating set with labeling
• Greedy approximations for minimum submodular cover with submodular cost
• Influence spread in social networks with both positive and negative influences
• New dominating sets in social networks
• On positive influence dominating sets in social networks
• Partitioning a graph into a dominating set, a total dominating set, and something else
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs

Cited in

(10)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Greedy approximation for the minimum connected dominating set with labeling
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• scientific article; zbMATH DE number 7724205 (Why is no real title available?)
• Connected dominating set in hypergraph
• A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
• A greedy approximation for minimum connected dominating sets
• A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks
• On parallelizing a greedy heuristic for finding small dominant sets
• A heuristic approximation algorithm of minimum dominating set based on rough set theory

This page was built for publication: A unified greedy approximation for several dominating set problems

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