Near-optimal dominating sets via random sampling

DOI10.1007/978-3-319-41168-2_14MaRDI QIDQ2830067zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Minimum connected dominating sets in finite graphs
• An efficient distributed algorithm for constructing small dominating sets
• Statistical mechanics of the minimum dominating set problem
• Approximation algorithms for connected dominating sets
• Analysis of a greedy heuristic for finding small dominating sets in graphs

Cites work

• Design and analysis of randomized algorithms. Introduction to design paradigms.
• Dominating sets in social network graphs
• Exact algorithms for dominating set
• Finite Dominating Sets for Network Location Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Inapproximability of dominating set on power law graphs
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Solving connected dominating set faster than \(2^n\)

Cited in

(7)

• Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem
• A heuristic approximation algorithm of minimum dominating set based on rough set theory
• Random procedures for dominating sets in bipartite graphs
• scientific article; zbMATH DE number 708868 (Why is no real title available?)
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• An order-based algorithm for minimum dominating set with application in graph mining
• Statistical mechanics of the minimum dominating set problem

This page was built for publication: Near-optimal dominating sets via random sampling

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