1 research outputs found
Parameterized Algorithms for the Min-Power Symmetric Connectivity Problem
No full textV bakalářské práci představíme problém Min Power Symmetric connectivity (MinPSC), který je na obecných grafech NP-těžký. Problém MinPSC má uplatněni v sítích, kde pro daný uzel chceme zmenšit jeho spotřebu energii na co nejmenší úroveň a požadujeme přitom, aby každý uzel mohl komunikovat s ostatními. V této práci zkoumáme problém MinPSC ze pohledu dvou strukturálních parametru. A to z vrcholového pokrytí a sousedské různorodosti.In this bachelor thesis, we introduce Min Power Symmetric Connectivity (MinPSC) problem which is NP-complete. The application of the problem is in networks, where we want to reduce a consumption of energy as much as possible. And while it is required to have a connection between each node in the network. In this thesis, we examine the problem MinPSC from the point of view of two structural graph parameters. Vertex cover and neighbourhood diversity
