Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
Modelujeme problém tvorby sítí z bezdrátových zařízení použitím identifikačních a lokalizačně-dominujících kódů na grafech jednotkového disku. Je známo, že minimalizace velikosti identifikačního kódu je MP-úplný problém byť i jen na bipartitních grafech.
Nejprve zobecníme výsledek na bipartitní rovinné grafy jednotkového disku. Pak se zaměříme na otázku existence identifikačního kódu pro náhodné grafy jednotkového disku.
Rozšíříme také výsledek ohledně NP-úplnosti minimalizace velikosti lokalizačně-dominujících kódů. Závěrem diskutujeme velikost těchto kódů na náhodných grafech jednotkového disku.