Near-Optimal Dominating Sets via Random Sampling

DOI10.1007/978-3-319-41168-2_14zbMath1476.68214OpenAlexW2488915139MaRDI QIDQ2830067

Martin Nehéz

Publication date: 9 November 2016

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-41168-2_14

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• Inapproximability of dominating set on power law graphs
• Solving connected dominating set faster than \(2^n\)
• Dominating sets in social network graphs
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• Finite Dominating Sets for Network Location Problems
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs