Graph Theory and Combinatorial Scientific Computing

Within this project, in cooperation with Faculty of Computer and Information Science (FRI), InnoRenew (SI) and Alfréd Rényi Institute of Mathematics (HU), we are identifying the problems related to the Combinatorial Scientific Computing and Graph Theory. We design and develop optimization algorithms that can be used on graph-based problems for execution on massively parallel computers. Special focus of the research is on connecting the theory with applications.

Project is focused on connecting applications with theory. The considered applications come from various fields, including combinatorial chemistry, system biology, marketing and portfolio analysis, engineering, social sciences and applied mathematics. From the theoretical point of view, the considered approaches include degree sequences, low degree graphs and trees, cliques and independent sets, graph functions such as connectivity, assortativity, girthness, randomness, colorings and community models. The theoretical and practical parts of the project support each other in this project: the applications contain practical problems for the theoretical research, whose aim is develop solutions and massively parallel procedures.

The main family of problems tackled by the project comes from NP-hard or NP-complete problems, which are some of the most difficult and sometimes intractable problems in the practice. For such problems, on one hand, often only a relatively good solution suffices if the true optimum is not reachable. On the other hand, some problems of this class have special properties which can be exploited to solve the problem exactly much faster. To deal whit these problems, the project approaches them in three steps. First the complexity of the problem is modelled, then the theoretical approaches to special problem properties are considered, and finally heuristic approaches for an approximate solution are attempted with theory providing good bounds on the solution for proving the solution quality.

Partners

Faculty of Computer and Information Science (FCI)

Jozef Stefan Institute (JSI)

InnoRenew CoE, an independent research institute situated in Slovenia

Alfréd Rényi Institute of Mathematics, the collaborating partner from Hungary

P-Lab team


Funding

Publications

M. Depolli, B. Zavalnij; Eliminating vertex coloring in clique search, MATCOS-22 : Middle-European Conference on Applied Theoretical Computer Science, 13-14 October 2022, Koper, Slovenia, 2022 [COBISS: 136099843]
J. Radešček, M. Depolli; Exact and approximate USCP with branch and bound, GECCO '21 : proceedings of the Genetic and Evolutionary Computation Conference Companion, 2021 [DOI: 10.1145/3449726.3463298][COBISS: 70736899]
J. Radešček, M. Depolli; Developer-centric design of branch and bound algorithm, MIPRO 2021 : 44th International Convention, September 27 - October 1, 2021, Opatija, Croatia, MIPRO ..., 2021 [COBISS: 81884675]