Ime strani: ARRSProjekti / 2021 / Teorija grafov in kombinatorično znanstveno računalništvo

Teorija grafov in kombinatorično znanstveno računalništvo

Nazaj na seznam za leto 2021


Oznaka in naziv projekta

N2-0171 Teorija grafov in kombinatorično znanstveno računalništvo
N2-0171 Graph Theory and Combinatorial Scientific Computing

Logotipi ARRS in drugih sofinancerjev

© Javna agencija za raziskovalno dejavnost Republike Slovenije

Projektna skupina

Vodja projekta: prof. dr. Andrej Brodnik

Sodelujoče raziskovalne organizacije: Povezava na SICRIS

Sestava projektne skupine: Povezava na SICRIS

Sodelujoče raziskovalne organizacije:

  1. Univerza v Ljubljani (Fakulteta za računalništvo in informatiko)
  2. Inštitut Jožef Stefan (soizvajalec)
  3. InnoRenew CoE Center odličnosti za raziskave in inovacije na področju obnovljivih materialov in zdravega bivanjskega okolja

Raziskovalci:

  • Andrej Brodnik (UL FRI)
  • Uroš Čibej (UL FRI)
  • Matjaž Depolli (IJS)
  • Tomaž Dobravec (UL FRI)
  • László Hajdu (InnoRenew)

  • Miklós Krész (InnoRenew)

  • Jurij Mihelič (UL FRI)
  • Borut Robič (UL FRI)
  • Boštjan Slivnik (UL FRI)

Vsebinski opis projekta

Vsebinski opis projekta

Glavni cilj projekta je opredelitev problemov s področja teorije grafov v okviru kombinatoričnega znanstvenega računalništva. Poseben poudarkom bo na povezovanju teoretičnega pristopa in praktične uporabe teoretičnih rešitev iz različnih področij. Slednja vključujejo kombinatorično kemijo, sistemsko biologijo, tržne in portfolio analize, klasične inženirske panoge, družbene vede, biomateriomiko in uporabno matematiko. Iz matematičnega zornega kota bodo uporabljena zaporedja vozlišč z monotono naraščajočimi stopnjami, grafi in drevesa z nizkimi stopnjami vozlišč, klike in neodvisne množice, grafne funkcije (povezljivost, naklonjenost, naključnost), različni tipi barvanja grafov in modelov skupnosti.

Naš cilj je načrtovanje (močno vzporednih optimizacijskih) algoritmov na grafih za reševanje omenjenih problemov in njihova implementacija na vzporednih računalniških okoljih. Projekt sestoji iz teoretičnega in praktičnega dela, ki se vzajemno dopolnjujeta: aplikacije definirajo najpomembnejše praktične probleme (ki pa so običajno preprostejši od povsem splošno zastavljenih problemov) in teoretično raziskovanje poskuša poiskati zakonitosti, katere veljajo v posebnem primeru, da lahko na njihovi osnovi razvijemo učinkovite rešitve za super-računalniške (vzporedne) sisteme. Čeprav bo teoretični del projekta v glavnem potekal na Rényijevem inštitutu v Budimpešti, razvoj algoritmov in njihova uporaba pa na univerzah v Ljubljani, Szegedu in Pécsu, bo sodelovanje obeh vej projekta glavni doprinos projekta.

Glavni problem je obstoj množice praktičnih problemov, ki so zelo zahtevni za reševanje (NP-težki in NP-polni), za katere so potrebne relativno dobre rešitve, saj ni mogoče poiskati optimalnih rešitev ali pa jih je možno najti samo pod določenimi posebnimi pogoji. Pristop k reševanju ima tri dele. Najprej je potrebno znati praktični problem ustrezno zmodelirati in oceniti računsko zahtevnost reševanja. Nato je v primeru težkih optimizacijskih in odločitvenih problemov potrebno preučiti po eni strani posebne primere in po drugi graf teoretične rezultate, ki bi vodili k razvoju učinkovitih algoritmov. Na koncu pa uporabimo še hevristične pristope za iskanje približnih rešitev s čim boljšo oceno ali dokazom kakovosti rešitve.

Predvideni rezultati so pomembni zaradi dveh stvari: najprej pričakujemo, da bodo imeli dejanski vpliv na področju teorije grafov oziroma na splošno na diskretno matematik; poleg tega in morda celo pomembneje, naj bi razviti algoritmi omogočili učinkovito reševanje praktičnih problemov z zgoraj naštetih področij.

Osnovni podatki sofinanciranja so dostopni na spletni strani SICRIS.

Faze projekta in opis njihove realizacije

1. Faza

2. Faza

3. Faza

Bibliografske reference


Nazaj na seznam za leto 2021