N1-0108 Discharging in Graph Domination

FMF - logo ang
ARRS - logo ang

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

Research Organisations


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.