Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0108
Naziv projekta: Prenos naboja v grafovski dominacij
Obdobje: 1. 2. 2019 - 30. 6. 2021
Letni obseg: 1 FTE, cenovna kategorija: E
Vodja: Csilla Bujtas
Veda: Naravoslovje
Vsebinski opis projekta :
Studying domination in graphs and designing better algorithms for this abstract mathematical problem allow us to solve many real-world problems more efficiently. The goal of the proposed research is twofold. It is planned to prove theoretical results, namely better upper bounds, on the domination number and to design effective algorithms which output dominating sets not greater than this upper bound.
The key innovative approach of this proposal that will enable improvement of best-known results is the following. Three already established methodologies will be used in a new combination and a new setting. First, as a unique approach, the discharging method for graph and hypergraph domination will be applied and combined with the weighting-greedy algorithmic method. Then, to get better estimations for large networks, the probabilistic method will be applied together with weight functions and/or discharging.
The proposed research will give rise to new theoretical results, new effective algorithms connected to applications, and it is designed to open a powerful new direction in the methodology applied in the domination theory.
