Teme v strukturni teoriji grafov: invariante, separatorji in presečne predstavitve / Topics in Structural Graph Theory: Invariants, Separators, and Intersection Representations
|
Naziv Tittle |
Teme v strukturni teoriji grafov: invariante, separatorji in presečne predstavitve / Topics in Structural Graph Theory: Invariants, Separators, and Intersection Representations |
|
Akronim Acronim |
N1-0102 |
|
Opis Description |
(SI) Ta projekt bo preučil več ključnih problemov znotraj čiste in algoritmične teorije grafov, s poudarkom na grafovskih invariantih in razredih grafov. Projekt se bo razvijal vzdolž treh medsebojno povezanih raziskovalnih tem: pogoji za obstoj funkcije, ki omejujejo eno invarianto v odvisnosti od druge, algoritmični vidiki izbranih grafovskih optimizacijskih problemov na ustreznih razredih grafov in sistematičen študij posplošitev tetivnosti. Napredek na teh problemih bo izhajal iz učinkovite kombinacije komplementarnih tehnik, ki se trenutno uporabljajo pri preučevanju razredov grafov, kot so: grafovski minorji, razcepi grafov, širinski parametri grafov, ekstremalna teorija grafov. (EN) This project will investigate several key problems within pure and algorithmic graph theory, with a focus on graph invariants and graph classes. It will be developed along three interconnected research lines: conditions for the existence of a function bounding one invariant in terms of another one, algorithmic aspects of selected graph optimization problems on resulting graph classes, and the development of a unifying framework for generalizations of chordality. Progresses on these problems will come from an effective combination of the complementary techniques that are currently used in the study of graph classes, such as graph minors, graph decompositions, graph width parameters, extremal graph theory. |
|
Vrsta projekta Project Type |
Projekti medn. sodelovanja |
|
Trajanje Duration |
01/05/2019 - 30/04/2023 |
|
URL URL |
https://p1-0285.iam.upr.si/sl/projekti/n1-0102 |
|
Vodja projekta Project Leader |
dr. Martin Milanič |
|
Sodelujoče organizacije Participating organizations |
/ |
|
Oddelek Department |
Oddelek za matematiko IAM |