Teorija grafov in kombinatorično znanstveno računalništvo
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
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:
- Univerza v Ljubljani (Fakulteta za računalništvo in informatiko)
- Inštitut Jožef Stefan (soizvajalec)
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