login
| EN

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
Univerza na Primorskem

Inštitut Andrej Marušič
UP IAM

Muzejski trg 2
6000 Koper
Slovenija

tel.: +386 (0)5 611 75 91
fax.: +386 (0)5 611 75 92
e-mail: info@iam.upr.si
Avtorske pravice
Izjava o dostopnosti