Our research group works at the interface of algorithmics, parallel/distributed computing,
and applications in networked systems. We often follow the methodology of
Algorithm Engineering. This means
to iterate the design, analysis, implementation, and systematic experimental evaluation
of algorithms. Our focus is on algorithms that are suitable for large problems and that
make use of the computational power of parallel systems. Three application areas are
of main interest, algorithmic network analysis, combinatorial scientific computing,
and applied combinatorial optimization. They are described in more detail below.
This area provides algorithms for investigating complex networks from a statistical
and structural point of view. It is currently funded by
DFG SPP Algorithms for Big Data.
Complex networks are used in many scientific areas as modelling tool.
Our algorithms are collected in our toolkit NetworKit and can, for example and among
many others, identify important nodes, generate synthetic networks, or compute natural
E. Bergamini, M. Borassi, P. Crescenzi, A. Marino, H. Meyerhenke: Computing Top-k Closeness Centrality Faster in Unweighted Graphs.
In Proc. 18th SIAM Algorithm Engineering & Experiments (ALENEX 2016).
[published version in SIAM epubs][preprint]
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 scientific computing methods. Our works
focus on load balancing of parallel graph and matrix algorithms -- which are for
example used in parallel numerical simulations.
H. Meyerhenke, B. Monien, T. Sauerwald:
A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions.
Journal of Parallel and Distributed Computing, 69(9):750-761, 2009.
Best Paper Awards and Panel Summary:
22nd International Parallel and Distributed Processing Symposium (IPDPS 2008).
[abstract][bibtex][preprint (pdf)][DOI: 10.1016/j.jpdc.2009.04.005]
Applied Combinatorial Optimization
This area addresses provably difficult problems that are often motivated by
applications in the (natural) sciences. Our aim is to solve larger problem instances
in a shorter time span, in particular by devising more efficient algorithms and by
employing parallel computation. Besides being interesting from an algorithmic point
of view, new solution techniques shall facilitate significant advancements in the
application domains. Recent examples of our topics include the assembly of DNA
sequences and protein structure determination -- both lead to NP-hard graph problems.
M. Wegner, O. Taubert, A. Schug, H. Meyerhenke:
Maxent-stress Optimization of 3D Biomolecular Models.
In Proc. 25th European Symposium on Algorithms (ESA 2017).
H. Meyerhenke, M. Nöllenburg, C. Schulz: Drawing Large
Graphs by Multilevel Maxent-Stress Optimization.
In Proc. 23rd International Symposium on Graph Drawing & Network Visualization (GD 2015).
Journal version to appear in IEEE TVCG.