• Graph Optimisation and Big Data
The Client : Javna agencija za raziskovalno dejavnost RS
Project duration: 2016 - 2019
  • Description

The main goal of the project is identifying problems related to the Big Data challenge in terms of graph models, proving theorems related to these parameters (chromatic number, independence number, etc.), designing (highly parallel optimization) graph algorithms for solving these models, and implementing them in exascale computing environments.

The project consists of theoretic and application oriented parts, but clearly, these parts are complementary: the applications pose the most important practical problems, that are typically simpler than the problems in their full generality, while the theoretical research tries to find theorems that can be applied in the particular question to develop a high performance computer effective procedures. The theoretical research is planned to carry out mainly by expert participants in Renyi Institute, and the algorithm designs by application oriented participants in Szeged, Pecs and Ljubljana, but clearly, the cooperation is the main power of the proposed project team.

The attacked problems that arose in practice are often proved to be very difficult or intractable (NP-hard or NP-complete) in their general form. But some relatively good solution is searched for even if the optimum cannot be achieved, or the optimum should be determined in the case of special conditions. This will be done partly by proving theorems and partly by finding solution algorithms with a sufficiently good performance.

The importance of the expected results is two-sided: they are expected to have a real importance in graph theory, or more general, in discrete mathematics, however, maybe even more important, the developed algorithms and procedures can be effectively applied on high performance computers and to cope with the Big Data problems.

Research activity

Engineering sciences and technologies

Range per year

0,63 FTE

Research organisations <http://www.sicris.si/public/jqm/prj.aspx?lang=eng&opdescr=search&opt=2&subopt=403&code1=cmn&code2=auto&psize=10&hits=1&page=1&count=&search_term=N2-0053&id=10073&slng=&order_by=>

Researchers <http://www.sicris.si/public/jqm/prj.aspx?lang=eng&opdescr=search&opt=2&subopt=402&code1=cmn&code2=auto&psize=10&hits=1&page=1&count=&search_term=N2-0053&id=10073&slng=&order_by=>

Project phases and their realization

There are no phases as it is a bilateral project.

Project bibliographic references

  • BRODNIK Andrej. Polypeptide origami. V: Abstracts, SWORDS 2017 - Szeged workshop on discrete structures, 23. 11. 2017 - 24. 11. 2017, Szeged, Hungary. Szeged: [University of Szeged]. 2017, 1 str. http://www.domlab.hu/swords2017/abstracts.html.
  • BRODNIK, Andrej, JOVIČIĆ, Vladan, PALANGETIĆ, Marko, SILADI, Daniel. Construction of Orthogonal CC-Set. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 36-39. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf.
  • BRODNIK, Andrej, GRGUROVIČ, Marko. Solving all-pairs shortest path by single-source computations : theory and practice. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2017, vol. 231, str. 119-130. https://doi.org/10.1016/j.dam.2017.03.008, doi: 10.1016/j.dam.2017.03.008. [COBISS.SI-ID 1540083908], [JCR, SNIP, WoS do 31. 1. 2018: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 31. 1. 2018: št. citatov (TC): 0, čistih citatov (CI): 0]
  • ČIBEJ, Uroš, MIHELIČ, Jurij. Adaptation and evaluation of the simplex algorithm for a data-flow architecture. V: HURSON, A. R. (ur.), MILUTINOVIĆ, Veljko (ur.). Advances in computers, (Advances in computers, ISSN 0065-2458, vol. 106). 1st ed. Cambridge (MA) [etc.]: Academic Press, an imprint of Elsevier. cop. 2017, str. 63-105, ilustr. http://www.sciencedirect.com/science/article/pii/S0065245817300153, doi: 10.1016/bs.adcom.2017.04.003. [COBISS.SI-ID 1537626051], [JCR, SNIP, WoS do 17. 11. 2017: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 3. 11. 2017: št. citatov (TC): 0, čistih citatov (CI): 0]
  • DEPOLLI, Matjaž, KONC, Janez, SZABÓ, Sándor, ZAVALNIJ, Bogdan. Usage of hereditary colorings of product graphs in clique search programs. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 40-43. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf. [COBISS.SI-ID 29895975]
  • DOBRAVEC, Tomaž. ALGator - an automatic algorithm evaluation system. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 28-31, ilustr. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf. [COBISS.SI-ID 1537311939]
  • DOBRAVEC, Tomaž, BULIĆ, Patricio. Comparing CPU and GPU implementations of a simple matrix multiplication algorithm. International journal of computer and electrical engineering, ISSN 1793-8163, Dec. 2017, vol. 9, no. 2, str. 430-438, ilustr. http://www.ijcee.org/index.php?m=content&c=index&a=show&catid=89&id=1091, doi: 10.17706/ijcee.2017.9.2.430-438. [COBISS.SI-ID 1537552067]
  • MIHELIČ, Jurij, ČIBEJ, Uroš. Experimental algorithmics for the dataflow architecture : guidelines and issues. The IPSI BGD Transactions on Advanced Research, ISSN 1820-4511, Jul. 2017, vol. 13, no. 1, str. 1-8, ilustr. http://tar.ipsitransactions.org/. [COBISS.SI-ID 1537327555]

Financed by

Slovenian Research Agency