The main goal of the project is to identify problems related to the Combinatorial Scientific Computing in connection with Graph Theory, and to design and implement optimization graph algorithms for solving these problems on massively parallel computers. Special focus of the research will be on connecting applications and theory. Applications come from various fields including combinatorial chemistry, system biology, market and portfolio analysis, engineering, social sciences, biomateriomics and applied mathematics. From a theoretical point of view we shall use degree sequences, low degree graphs and trees, cliques and independent sets, graph functions (connectivity, assortativity, girthiness, randomness), different types of graph colorings and community models. Although the project will consist of theoretical and applicative parts, these parts will support each other: the applications contain the most important practical problems (that are typically somewhat simpler than the problems in full generality) and the theoretical research is supposed to yield results that can be applied to develop an effective massively parallel procedures. The theoretical research is to be carried out mainly by the participants at Rényi Institute while the algorithm design is planned at Szeged, Pécs and Ljubljana. However, cooperation is the main power of the project.

The main problem is that several problems arose in practice which are proved to be very difficult or even intractable (NP-hard or NP-complete). Often some relatively good solution is needed even if the optimum cannot be determined or if it can be determined only for special cases of a problem. Our goal is threefold. First, we shall model each application in question and determine the computational complexity of the problem. Second, in case of hard optimization and decision problems we shall look for special cases and graph theoretic approach for developing effective algorithms. Third, we shall use heuristic approaches for finding approximate solutions and good bounds for proving their quality.

The anticipated results are important for two reasons. First, they are expected to have real importance in graph theory or in general in discrete mathematics. Second, and perhaps even more important, the developed algorithms and procedures can be used in applications effectively.

Research activity

Engineering sciences and technologies

Range on year

0,56 FTE

Research organisations

Jožef Stefan Institut [IJS]

InnoRenew CoE Renewable Materials and Healthy Environments Research and Innovation Centre of Excellence [InnoRenew]

Researchers

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)

Project phases and their realization

Project bibliographic references

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]

Financed by

Slovenian Research Agency