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.

Veda

Tehnika

Letni obseg

0,56 FTE

Sodelujoče raziskovalne organizacije

Institut Jožef Stefan [IJS]

InnoRenew CoE Center odličnosti za raziskave in inovacije na področju obnovljivih materialov in zdravega bivanjskega okolja [InnoRenew]

Sestava projektne skupine

Andrej Brodnik (UL FRI)

Uroš Čibej(UL FRI)

Tomaž Dobravec (UL FRI)

Jurij Mihelič(UL FRI)

Borut Robič(UL FRI)

Boštjan Slivnik(UL FRI)

Matjaž Depolli(IJS)

László Hajdu(InnoRenew)

Miklós Krész (InnoRenew)

Faze projekta

Bibliografske reference projekta

BABIČ, Matej, MIHELIČ, Jurij, CALÌ, Michele. Complex network characterization using graph theory and fractal geometry: the case study of lung cancer DNA sequences. Applied sciences. 2020, vol. 10 (https://www.mdpi.com/2076-3417/10/9/3037). [COBISS.SI-ID 12929539]

BRODNIK, Andrej, GRGUROVIČ, Marko. Parallelization of ant system for GPU under the PRAM model. Computing and informatics. 2018, vol. 37, no. 1 (http://www.cai.sk/ojs/index.php/cai/article/view/2018_1_229). [COBISS.SI-ID 1537873347]

BRODNIK, Andrej, GRGUROVIČ, Marko. Practical algorithms for the all-pairs shortest path problem. V: ADAMATZKY, Andrew. Shortest path solvers: from software to wetware. Springer, 2018. (https://link.springer.com/chapter/10.1007/978-3-319-77510-4_6). [COBISS.SI-ID 1537800131]

BRODNIK, Andrej, JEKOVEC, Matevž. Sliding suffix tree. Algorithms. 2018, vol. 11, no. 8 (http://www.mdpi.com/1999-4893/11/8/118/htm). [COBISS.SI-ID 1537905347]

BURNARD, Michael David, TAVZES, Črtomir, TOŠIĆ, Aleksandar, BRODNIK, Andrej, KUTNAR, Andreja. The role of reverse logistics in recycling of wood products. V: MUTHU, Subramanian Senthilkannan. Environmental implications of recycling and recycled products. Springer, 2015 (DOI: 10.1007/978-984-287-643-0_1). [COBISS.SI-ID 1537733060]

MIHELIČ, Jurij, ČIBEJ, Uroš. An experimental evaluation of refinement techniques for the subgraph isomorphism backtracking algorithms. Open computer science. Jan. 2021, vol. 11, no. 1 (https://www.degruyter.com/view/journals/comp/11/1/article-p33.xml?tab_body=abstract). [COBISS.SI-ID 44439043]

ČIBEJ, Uroš, MIHELIČ, Jurij. Graph automorphisms for compression. Open computer science. Jan. 2021, vol. 11, no. 1 (https://www.degruyter.com/view/journals/comp/11/1/article-p51.xml?tab_body=pdf-79549). [COBISS.SI-ID 44438019]

ČIBEJ, Uroš, MIHELIČ, Jurij. Two classes of graphs with symmetries allowing a compact representation. V: Informatics 2019 (https://ieeexplore.ieee.org/document/9119294). [COBISS.SI-ID 20320259]

MIHELIČ, Jurij, ČIBEJ, Uroš. Matrix-based algorithms for dataflow computer architecture : an overview and comparison. V: MILUTINOVIĆ, Veljko (ur.), KOTLAR, Milos (ur.). Exploring the DataFlow supercomputing paradigm: example algorithms for selected applications. Springer, 2019 (https://link.springer.com/chapter/10.1007/978-3-030-13803-5_4). [COBISS.SI-ID 1538246851]

ROBIČ, Borut. The foundations of computability theory, 2nd ed. Springer, 2020.

TROBEC, Roman, SLIVNIK, Boštjan, BULIĆ, Patricio, ROBIČ, Borut. Introduction to parallel computing: from algorithms to programming on state-of-the-art platforms. Springer 2018 (https://link.springer.com/book/10.1007%2F978-3-319-98833-7). [COBISS.SI-ID 1537870275]

Financerji

Javna agencija za raziskovalno dejavnost Republike Slovenije