Our group tackles a broad spectrum of scalable graph algorithms in particular in the context of very large inputs. In general, our research is based on four pillars: multilevel algorithms, practical kernelization, parallelization and memetic algorithms that are highly interconnected. To this end, our group engineers algorithms that improve known methods. Typically, we release the techniques and algorithms developed as easy-to-use open source software. Examples include a widely used library of algorithms for graph partitioning, graph drawing, (weighted) independent sets, hypergraph partitioning, graph clustering, graph generation, minimum cuts, process mapping and many more.

News

    17.6.2021: We released a new technical report "High Quality Hypergraph Partitioning" joint work with Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz and Peter Sanders. This paper considers the balanced hypergraph partitioning problem. In the TR, we describe all details of our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach. You can find a preprint here.

    9.6.2021: Prof. Dr. Christian Schulz will be PC Chair for the PACE'22 implementation challenge. Ernestine Grossmann, Tobias Heuer and Darren Strash are joining the program committee.

    6.5.2021: We released a new technical report on "Deep Multilevel Graph Partitioning" by Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, Daniel Seemaier. You can find a preprint here.

    6.5.2021: Two papers of the group have been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21). The paper "Fully-dynamic Weighted Matching Approximation in Practice" by Eugenio Angriman, Henning Meyerhenke, Christian Schulz, Bora Ucar and the paper "Faster Parallel Multiterminal Cuts" by Monika Henzinger, Alexander Noe, Christian Schulz.

    29.4.2021: The paper "An MPI-Parallel Algorithm for Mapping Complex Networks onto Hierarchical Architectures" by Maria Predarim, Charilaos Tzovas, Christian Schulz, Henning Meyerhenke has been accepted for publication at the 27th International European Conference on Parallel Computing (Euro-Par).

    28.4.2021: We released a new technical report on "Fully-dynamic Weighted Matching Approximation in Practice" joint work with Eugenio Angriman, Henning Meyerhenke, Christian Schulz and Bora Ucar. You can find a preprint here.

    9.3.2021: The paper "O'Reach: Even Faster Reachability in Large Graphs" by Kathrin Hanauer, Christian Schulz and Jonathan Trummer has been accepted for publication at the 19th Symposium on Experimental Algorithms (SEA). You can find a preprint here.

    1.3.2021: Our survey ``Recent Advances in Scalable Graph Generation'' together with Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders and Christian Schulz has been accepted as a book chapter for the Massive Graph Analytics book. You can find a preprint here.

    23.2.2021: We released a new survey on fully dynamic graph algorithms. You can find it here.

    19.2.2021: We released a new TR on buffered streaming graph partitioning. Faster and better than the previous state-of-the-art! You can find it here.

    1.2.2021: We have new group member, Ernestine Grossmann -- Welcome!

    23.12.2020: We released a survey on recent advances in practical data reduction. It is available here.

    16.11.2020: We released mt-KaHIP -- shared-memory parallel high quality graph partitioning. It can be found here.

    10.11.2020: One paper of the group ``The Future is Big Graphs! A Community View on Graph Processing Systems'' together with Sakr et. al has been accepted at Communications of ACM (CACM). A preprint can be found here.

    5.10.2020: Four papers of the group have been accepted at SIAM Symposium on Algorithm Engineering and Experiments (ALENEX21).

    1.10.2020: Covid-19: Due to the ongoing Coronavirus situation, lectures and seminars in the upcomping winter semester 2020/21 will be done online.

    1.10.2020: We started! On October 1st, our group arrived in the new offices in Heidelberg. In somnis veritas.