Grafovske strukture in učinkoviti algoritmi za optimizacijske probleme / Graph structures and efficient algorithms for optimization problems

(SI) Nemški partnerji bodo prispevali predvsem k algoritmični strani projekta, s svojim strokovnim znanjem o uporabi grafovskih pregledovanj za razvoj hitrih algoritmov na grafih. Veliko teh algoritmov sloni tudi na linearnih razvrstitvah vozlišč. Slovenska stran pa je specializirana za strukturno teorijo grafov. To vključuje raziskave grafovskih razredov, definiranih z omejitvami na klike in/ali neodvisne množice, strukturne lastnosti problemov neodvisne in dominantne množice ter produktne grafe in grafe z visoko stopnjo simetrije. Projekt se bo izvajal z izr. prof. Martinom Milaničem in prof. dr. Ekkehardom Köhlerjem kot vodilnima raziskovalcema. Projekt bo pomemben korak k utrditvi nedavno vzpostavljenega sodelovanja med matematiki v Kopru in Cottbusu.

(EN) 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 Slovenian side, on the other hand, is specialized in structural graph theory. This includes research on graph classes defined with constraints imposed on cliques and/or independent sets, structural properties of the maximum independent set and domination problems, as well as product graphs and graphs with high degrees of symmetry. The project will be an important step towards a consolidation of the recently established cooperation between mathematicians in Koper and Cottbus.