Meno:  Jozef


Priezvisko:  Spišiak


Názov:  Local construction of dominating set


Vedúci:  RNDr. Stefan Dobrev, PhD.


Rok:  2011


Blok:  INF


Kľúčové slová:  dominating set, graph theory, NPcomplete problem, local algorithm, wireless networks


Abstrakt:  This thesis handles the local construction of dominating set problem. It’s
core is being constructed on local algorithm for ﬁnding this set on graph
(network), analyzing the algorithm input parameters. Statistical research
determines effectiveness of algorithm and its variants (modifications). Chapter
7 shows the improvement for this algorithm generating smaller dominating
set. It visualizes this algorithm and also provides reader with helpful source
codes made for this work. It also contains examples written in programming
language C++. It shows which algorithms are best for using on networks,
depending on the density of network.

