Research

Attention: Websites still under construction

Research focus

The research group headed by Prof. Dr. Henning Meyerhenke deals with questions and methods of parallel/distributed algorithm technology. We develop, analyze and implement practical and theoretically sound scalable discrete algorithms for large and complex networked systems. Of particular importance are graph algorithms.

Our current focus is on the following areas:

  • Algorithmic analysis of large complex networks, especially considering dynamic changes

  • Combinatorial scientific computing, in particular graph partitioning and load balancing as well as scheduling

  • Applied optimization, especially for algorithmically difficult problems from the natural sciences

A (very small) part of our research results are also available on our Youtube channel, which was created during our affiliation with HU Berlin. The selected publications below are still being updated as part of the rebuilding of our KIT web pages.


Algorithmic Network Analysis

This area deals with the structural analysis of complex networks and has been supported over the years by various third-party funded projects of the DFG and the MWK Baden-Württemberg. Complex networks have proven themselves as a modeling tool in many areas of science. Their statistical analysis using mathematical and applied algorithmic methods provides deeper insights into the structural context of the modeled entities and their connections. For example, our algorithms can identify important individuals in a social network or reveal the natural group structure of the network. The implementations of our algorithms are bundled in the software NetworKit, which is developed open source under our leadership and used internationally (> 300 repositories on github were using NetworKit in early 2025).

Selected publications:
  • E. Bergamini, P. Crescenzi, G. D'Angelo, H. Meyerhenke, L. Severini, Y. Velaj: Improving the Betweenness Centrality of a Node by Adding Links. In ACM Journal of Experimental Algorithmics 23 (2018).
    [DOI: 10.1145/3166071]
  • E. Bergamini, H. Meyerhenke: Approximating Betweenness Centrality in Fully-dynamic Networks. In Internet Mathematics 12(5): 281-314 (2016). Taylor and Francis Group.
    [arXiv preprint] [DOI: 10.1080/15427951.2016.1177802]
  • C.L. Staudt, A. Sazonovs, H. Meyerhenke: NetworKit: A Tool Suite for Large-scale Network Analysis. In Network Science 4(4), pp. 508-530, December 2016. Cambridge University Press.
    [preliminary version at arXiv] [DOI: 10.1017/nws.2016.20]
  • C.L. Staudt, H. Meyerhenke: Engineering Parallel Algorithms for Community Detection in Massive Networks. IEEE Transactions on Parallel and Distributed Systems vol. 27, no. 1, pp. 171-184, 2016. Extended and updated version of ICPP'13 paper.
    [arXiv preprint] [DOI: 10.1109/TPDS.2015.2390633] (c) 2015 IEEE


Combinatorial scientific computing

This area develops theoretical foundations, combinatorial algorithms and tools that contribute to the improvement of parallel methods of scientific computing. In particular, the load balancing of parallel graph and matrix algorithms, such as those used in numerical simulations, should be mentioned here. As part of the DFG project TEAM and the BMBF project WAVE, we developed methods that map such and similar simulations to parallel computers in such a way that each processor has the same workload and has to communicate as little as possible with other processors. In this context, we are also looking at application-oriented scheduling methods in the DFG Collaborative Research Center 1404 FONDA.

Selected publications:


Applied combinatorial optimization

This (comparatively small) area deals with provably difficult algorithmic problems that are often motivated by scientific applications. Here we want to solve larger problem instances in shorter time (approximately) by innovative and usually parallel algorithms and thus enable new progress in the application sciences.

Selected publications: