Bachelor theses
Parameterized Algorithms for the Min-Power Symmetric Connectivity Problem
Author
Daniel Dajbov
Year
2024
Type
Bachelor thesis
Supervisor
Mgr. Michal Opler, Ph.D.
Reviewers
doc. RNDr. Dušan Knop, Ph.D.
Department
Summary
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.