Forschung

Eine Übersicht unserer Drittmittelprojekte finden Sie hier.

Allgemeiner Überblick

Die Arbeitsgruppe Theoretische Informatik und Paralleles Rechnen von Henning Meyerhenke arbeitet an den Schnittstellen von Algorithmik, parallelem Rechnen und Anwendungen in vernetzten Systemen. Methodisch orientieren wir uns am zyklischen Vorgehen des Algorithm Engineering. Dabei werden Entwurf, Analyse, Implementierung und systematische experimentelle Evaluation von Algorithmen iteriert. Im Vordergrund stehen dabei Algorithmen, die für große Problemstellungen geeignet sind und die Rechenleistung paralleler Systeme nutzen. Inhaltlich arbeitet die Gruppe in den drei unten aufgeführten Anwendungsfeldern.

Algorithmische Netzwerkanalyse

Dieser Bereich befasst sich mit der strukturellen Untersuchung komplexer Netzwerke und wird momentan durch das DFG SPP Algorithms for Big Data gefördert. Komplexe Netzwerke haben sich in vielen Bereichen der Wissenschaft als Modellierungswerkzeug bewährt. Ihre statistische Analyse mit mathematischen und angewandten algorithmischen Methoden liefert tiefere Einsichten über den strukturellen Zusammenhang der modellierten Entitäten und ihrer Verbindungen. Beispielsweise können durch unsere Algorithmen wichtige Personen in einem sozialen Netzwerk identifiziert oder die natürliche Gruppenstruktur des Netzwerks erkennbar gemacht werden. Die Implementierungen unserer Algorithmen werden in der Software NetworKit gebündelt, die unter unserer Federführung quelloffen entwickelt und international eingesetzt wird.

Ausgewählte Veröffentlichungen:

  • 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]
  • 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

Kombinatorisches wissenschaftliches Rechnen

Dieser Bereich entwickelt theoretische Grundlagen, kombinatorische Algorithmen und Tools, die zur Verbesserung paralleler Methoden des wissenschaftlichen Rechnens beitragen. Hier ist insbesondere die Lastbalancierung von parallelen Graphen- und Matrixalgorithmen zu nennen, wie sie etwa in numerischen Simulationen verwendet werden. Im Rahmen des DFG-Projektes TEAM entwickeln wir Methoden, die solche und ähnliche Simulationen derartig auf Parallelrechner abbilden, dass jeder Prozessor gleich viel Arbeitslast hat und möglichst wenig mit anderen Prozessoren kommunizieren muss.

Ausgewählte Veröffentlichungen:

Angewandte kombinatorische Optimierung

Dieser Bereich beschäftigt sich mit beweisbar schwierigen algorithmischen Problemstellungen, die oft durch naturwissenschaftliche Anwendungen motiviert sind. Hier wollen wir durch innovative und in der Regel parallele Algorithmen größere Probleminstanzen in kürzerer Zeit lösen und so neue Fortschritte in den Anwendungswissenschaften ermöglichen. Ein Beispiel aus der näheren Vergangenheit ist die Assemblierung von DNA-Sequenzen, die man sich als das Lösen eines gigantischen Puzzles vorstellen kann, bei dem sich viele Teile ähnlich sehen.

Ausgewählte Veröffentlichungen:

  • M. Wegner, O. Taubert, A. Schug, H. Meyerhenke: Maxent-stress Optimization of 3D Biomolecular Models. In Proc. 25th European Symposium on Algorithms (ESA 2017). To appear.
    [arXiv preprint]
  • 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). [arXiv preprint]
  • X. Liu, P. R. Pande, H. Meyerhenke, D.A. Bader: PASQUAL: Parallel Techniques for Next Generation Genome Sequence Assembly. IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 5, pp. 977-986, May 2013. [abstract] [bibtex] [preprint (pdf)] [supplementary material (pdf)] [DOI: 10.1109/TPDS.2012.190]