Iskanje v grafih, grafovski razredi in posplošitev tetivnosti / Graph searching, graph classes, and generalizations of chordality
|
Naziv Tittle |
Iskanje v grafih, grafovski razredi in posplošitev tetivnosti / Graph searching, graph classes, and generalizations of chordality |
|
Akronim Acronim |
BI-DE/19-20-007 |
|
Opis Description |
(SI) Prispevek obeh raziskovalnih skupin: Slovenska stran je specializirana za strukturno teorijo grafov in ima med drugim izrazite izkušnje z grafovskimi razredi, definiranimi prek omejitev nad klikami in/ali neodvisnimi množicami, razredi zaprtimi za inducirane minorje, še posebej za družine grafov, izpeljane iz strukturnih lastnosti, povezanih s problemi neodvisne množice in dominacije. Pomemben prispevek nemške partnerske institucije predstavlja njihovo izvrstno poznavanje grafovskih iskanj za načrtovanje hitrih grafovskih algoritmov, kot tudi uporabe različnih linearnih urejenosti nad množico vozlišč. Poleg tega ima skupina iz Cottbusa izkušnje v teoriji AT-prostih grafov ter sorodnih razredov (neprimerljivostnih grafov, intervalnih grafov, permutacijskih grafov ipd.). Komplementarnost omenjenih kompetenc je ključna za dosego omenjenih ciljev projekta, pri čemer nekolikšna sorodnost zagotavlja kompatibilno sodelovanje ter izmenjavo izkušenj med raziskovalnima skupinama. (EN) Contributions of each side: The Slovenian side is specialized in structural graph theory. This includes research on graph classes defined with constraints imposed on cliques and/or independent sets, graph classes closed under induced minors, and structural properties related to the maximum independent set problem and variants of domination. On the other hand, the German partners will contribute to the algorithmic side, using their expertise in the use of graph searches in the development of fast graph algorithms, many of which have also relied on linear vertex orderings. The Cottbus group also offers experience in the theory of AT-free graphs and related classes (co-comparability graphs, interval graphs, permutation graphs, etc.). These combined competencies will be essential to the achievement of the stated project goals, while the similarities in both research profiles promise straightforward cooperation with much common ground. |
|
Trajanje Duration |
01/01/2019 - 31/12/2021 |
|
Vodja projekta Project Leader |
Martin Milanič |
|
Sodelujoče organizacije Participating organizations |
BTU Cottbus-Senftenberg |
|
Oddelek Department |
Oddelek za matematiko IAM |