N1-0108 Prenos naboja v grafovski dominaciji

FMF - logo
ARRS - logo

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

Sodelujoče RO

Sestava projektne skupine

Bibliografske reference

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.