Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: N1-0108
Project: Discharging in Graph Domination
Period: 1. 2. 2019 - 31. 1. 2021
Range per year: 1 FTE, category: E
Head: Csilla Bujtas
Research activity: Natural sciences and mathematics
Citations for bibliographic records
Project description:
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.
