Seminár z teoretickej informatiky - Martin Nehéz (11.3.2016)

v piatok 11.3.2016 o 11:00 hod. v miestnosti M/213

---

Prednášajúci: Martin Nehéz

Názov: Near-Optimal Dominating Sets via Random Sampling

Termín: 11.3.2016, 11:00 hod., M/213

Abstrakt:
Motivated by the transportation, social and biological networks from a control theory perspective, the main result of this talk is the assertion that a random set with a given number of vertices (greater than the size of the corresponding MDS) has a relatively high probability of being a dominating set.
It implies that a simple Monte Carlo randomized algorithm can compute a near-optimal dominating set with high probability and its time complexity is moderately exponential, i.e. $O^*(t^n)$, where $t$ depends both on the constant approximation ratio $rho$ and the domination number $gamma$ of an input graph.
Although such a time complexity is not polynomial, our result might be of significance in particular contexts where exact algorithms cannot be run, e.g. in distributed computation environments.
Additionally, we present an experimental evaluation of 3 different algorithms for dominating set computation.

---