Ehemalige Fachgruppe »Algorithmen und Komplexität« des Heinz Nixdorf Institut
Prof. Dr. Friedhelm Meyer auf der Heide
„Hohe Rechenleistung kann nur durch eine Kombination von leistungsfähigen Computersystemen und Algorithmen, die das gegebene Problem so effizient wie möglich lösen, erreicht werden. Daher hat sich die Entwicklung von effizienten Algorithmen als klassischer Zweig der Informatik etabliert.”
Hohe Rechenleistung = Innovative Computersysteme + Effiziente Algorithmen
Unsere Forschung konzentriert sich auf Fragestellungen, in denen aktuelle technische Möglichkeiten, wie z. B. Hochleistungsrechnernetzwerke, drahtlose, mobile Kommunikationsnetze oder durch Spezialhardware unterstützte Systeme, neue Herausforderungen für den Entwurf effizienter Algorithmen darstellen.
Prof. Dr. Friedhelm Meyer auf der Heide ist seit dem 1.8.2023 in Pension. Deshalb vergeben wir keine Bachelor- und Masterarbeiten und auch keine Internships mehr. Die wissenschaftlichen Mitarbeiter sind ab dem 1.8.2023 Mitglieder der Arbeitsgruppe von Prof. Dr. Christian Scheideler.
Bilder der Arbeitsgruppe
Curriculum Vitae – Friedhelm Meyer auf der Heide
Friedhelm Meyer auf der Heide ist seit 1989 Professor für Algorithmen und Komplexität am Heinz Nixdorf Institut und am Institut für Informatik der Fakultät für Elektrotechnik, Informatik und Mathematik der Universität Paderborn. Er promovierte 1981 an der Universität Bielefeld in Mathematik und habilitierte sich 1986 an der Johann Wolfgang Goethe-Universität Frankfurt in Informatik. Von 1984 bis 1985 war er Gastforscher bei IBM Research in San Jose, Kalifornien, USA. 1986 bis 1989 arbeitete er als Professor (C3) für Theoretische Informatik in Dortmund und wechselte von dort nach Paderborn. Seit 2023 ist er pensioniert.
1986 wurde ihm der Preis für die beste Habilitation der Johann Wolfgang Goethe-Universität Frankfurt verliehen. 1992 wurde er gemeinsam mit seinem Kollegen Burkhard Monien mit dem Leibniz-Preis der Deutschen Forschungsgemeinschaft ausgezeichnet. 2007 wurde er in die Deutschen Akademie der Naturforscher »Leopoldina«, 2013 in die Nordrhein-Westfälische Akademie der Wissenschaften und der Künste und 2017 in die Deutsche Akademie der Technikwissenschaften »acatech« aufgenommen. 2021 wurde er mit dem »Prize for Innovation in Distributed Computing« der SIROCCO ausgezeichnet und 2024 zum EATCS-Fellow ernannt.
Friedhelm Meyer auf der Heide war Sprecher des DFG-Graduiertenkollegs »Parallele Rechnernetze in der Produktionstechnik« (1992–2001), der Sonderforschungsbereiche 376 »Massive Parallelität« (1995–2006) und 901 »On the Fly Computing« (2011–2023) sowie Koordinator des EU-Integrierten Projekts »Dynamically Evolving Large Scale Information Systems (DELIS)« (2004–2008). Er war in verschiedenen Funktionen für die DFG tätig, u. a. als Mitglied des Fachkollegiums Informatik (2000–2008), des Heisenberg-Ausschusses und des DFG-DAAD Programms »Promotion an Hochschulen in Deutschland« (2003, 2008). Zudem war er Mitglied des wissenschaftlichen Direktoriums des Leibniz-Zentrums für Informatik »Schloss Dagstuhl« (2005–2008) und des Fachbeirats des Max-Planck-Instituts für Informatik, Saarbrücken (2001–2011) sowie General Chair der ACM-Symposiums-Reihe »Parallelism in Algorithms and Architectures (SPAA)« (2007–2011), Leiter der Bundes-Jury Mathematik/Informatik des Bundeswettbewerbs »Jugend Forscht« (2007–2016) und Vorsitzender des Wissenschaftlichen Beirats des Leibniz-Zentrums für Informatik »Schloss Dagstuhl« (2014–2021). Er war Mitglied zahlreicher Programmkomitees, als Leiter u. a. für die Tagungen SPAA, ICALP und ESA.
Seine Forschungsinteressen beinhalten algorithmische und komplexitätstheoretische Fragestellungen zu parallelem Rechnen, Kommunikation und Datenverwaltung in Netzwerken, Dynamik in Netzwerken, Algorithmen der Computergrafik sowie Randomisierungsmethoden. Er ist (Co-)Autor von über 200 Publikationen und mehreren Patenten. Bisher wurden über 50 von ihm betreute Promotionen abgeschlossen, 14 seiner Schüler haben mittlerweile Professuren inne.
Publikationen von Prof. Dr. Friedhelm Meyer auf der Heide
A comparison of two variations of a pebble game on graphs
F. Meyer auf der Heide, Automata, Languages and Programming. ICALP 1979 (1979) 411–421.
Untere Zeitschranken für das Rucksack-Problem
P. Klein, F. Meyer auf der Heide, in: GI - 10. Jahrestagung, Berlin, Heidelberg, 1980.
Random access machines and straight-line programs
F. Meyer auf der Heide, A. Rollik, in: Fundamentals of Computation Theory, Berlin, Heidelberg, 1981.
Time-processor trade-offs for universal parallel computers
F. Meyer auf der Heide, in: Lecture Notes in Computer Science, Berlin, Heidelberg, 1981.
A comparison of two variations of a pebble game on graphs
F. Meyer auf der Heide, Theoretical Computer Science (1981) 315–322.
Alle Publikationen anzeigen
Publikationen der Fachgruppe
A comparison of two variations of a pebble game on graphs
F. Meyer auf der Heide, Automata, Languages and Programming. ICALP 1979 (1979) 411–421.
Untere Zeitschranken für das Rucksack-Problem
P. Klein, F. Meyer auf der Heide, in: GI - 10. Jahrestagung, Berlin, Heidelberg, 1980.
Random access machines and straight-line programs
F. Meyer auf der Heide, A. Rollik, in: Fundamentals of Computation Theory, Berlin, Heidelberg, 1981.
Time-processor trade-offs for universal parallel computers
F. Meyer auf der Heide, in: Lecture Notes in Computer Science, Berlin, Heidelberg, 1981.
A comparison of two variations of a pebble game on graphs
F. Meyer auf der Heide, Theoretical Computer Science (1981) 315–322.
Alle Publikationen anzeigen
Promotionen und Habilitationen der Fachgruppe
Promotionen
- Jonas Harbig: Forming Large Patterns from Widespread Swarms of Oblivious Robots with Limited Visibility, 31.07.2025
Promotionen
- Simon Pukrop: On Cloud Assisted, Restricted, and Resource Constrained Scheduling, 26.06.2023
- Till Knollman: Online Algorithms for Allocating Heterogeneous Resources, 30.05.2023
- Jannik Castenow: Local Protocols for Contracting and Expanding Robot Formation Problems, 24.05.2023
Promotionen
- Björn Feldkord: Mobile Resource Allocation, 23.01.2020
Promotionen
- Alexander Mäcker: On Scheduling with Setup Times, 06.11.2019
- Manuel Malatyali: Big Data: Sublinear Algorithms for Distributed Data Streams, 15.02.2019
Promotionen
- Matthias Feldotto: Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games, 21.12.2018
- Daniel Jung: Local Strategies for Swarm Formations on a Grid, 13.02.2018
Promotionen
- Sören Riechers: Scheduling with Scarce Resources, 14.11.2017
- Pavel Podlipyan: Local Algorithms for the Continuous Gathering Problem, 08.11.2017
- Shouwei Li: Parallel fixed parameter tractable problems, 12.10.2017
Promotionen
- Max Drees: Existence and Properties of Pure Nash Equilibria in Budget Games, 27.06.2016
- Andreas Cord-Landwehr: Selfish Network Creation - On Variants of Network Creation Games, 09.02.2016
Promotionen
- Christine Markarian: Online Resource Leasing, 08.07.2015
- Claudius Jähn: Bewertung von Renderingalgorithmen
für komplexe 3-D-Szenen, 25.06.2015 - Sebastian Abshoff: On the Complexity of Fundamental Problems in
Dynamic Ad-hoc Networks, 27.04.2015
Promotionen
- Peter Kling: Energy-efficient Scheduling Algorithms, 31.03.2014
- Ralf Petring: Multi-Algorithmen-Rendering: Darstellung heterogener 3-D-Szenen in Echtzeit, 14.02.2014
Promotionen
- Benjamin Eikel: Spherical visibility sampling : preprocessed visibility for occlusion culling in complex 3D scenes, 18.12.2013
- Peter Pietrzyk: Local and Online Algorithms for Facility Location, 28.10.2013
Promotionen
- Barbara Kempkes: Local strategies for robot formation problems, 17.02.2012
Promotionen
- Tim Süß: Parallel Real-Time Rendering using Heterogeneous PC Clusters, 19.12.2011
- Sascha Effert: Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen, 10.05.2011
- Joachim Gehweiler: Peer-to-Peer Based Parallel Web Computing, 09.05.2011
Promotionen
- Jan Mehler: Power-Aware Online File Allocation in Dynamic Networks, 30.09.2010
- Peter Mahlmann: Peer-to-Peer Networks based on Random Graphs, 13.04.2010
- Sebastian Degener: Local, distributed approximation algorithms for geometric assignment problems, 13.04.2010
Promotionen
- Katharina Lürwer-Brüggemeier: Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division, 17.12.2008
- Mario Mense: On Fault-Tolerant Data Placement in Storage Networks, 16.12.2008
- Gunnar Schomaker: Distributed Resource Allocation and Management in Heterogeneous Networks, 16.12.2008
- Michael Kortenjan: Size Equivalent Cluster Trees - Rendering CAD Models in Industrial Scenes, 14.11.2008
- Olaf Bonorden: Versatility of Bulk Synchronous Parallel Computing: From the Heterogeneous Cluster to the System on Chip, 30.05.2008
Habilitationen
- Martin Ziegler: Real Computability and Hypercomputation, 14.3.2008
Promotionen
- Jaroslaw Kutylowski: Using Mobile Relays for Ensuring Connectivity in Sparse Networks, 06.12.2007
- Miroslaw Dynia: Collective Graph Exploration, 06.12.2007
Promotionen
- Gereon Frahling: Algorithms for Dynamic Geometric Data Streams, 18.10.2006
- Stefan Rührup: Position-based Routing Strategies, 31.08.2006
- Miroslaw Korzeniowski: Dynamic Load Balancing in Peer-to-Peer Networks, 05.05.2006
- Valentina Damerow: Average and Smoothed Complexity of Geometric Structures, 03.03.2006
Promotionen
- Marcin Bienkowski: Page Migration in Dynamic Networks, 16.09.2005
- Jan Klein: Efficient Collision Detection for Point and Polygon Based Models, 22.07.2005
- Klaus Volbert: Geometric Spanners for Topology Control in Wireless Networks, 14.06.2005
- Matthias Fischer: Design, Analysis, and Evaluation of a Data Structure for Distributed Virtual Environments, 18.03.2005
Promotionen
- Kay Salzwedel: Data Distribution Algorithms for Storage Networks, 16.07.2004
Promotionen
- Harald Räcke: Data management and routing in general networks, 08.12.2003
Promotionen
- Christian Sohler: Property Testing and Geometry, 18.12.2002
- Martin Ziegler: Zur Berechenbarkeit reeller geometrischer Probleme, 11.11.2002
Habilitationen
- Christian Schindelhauer: Communication Network Problems, 9.2002
Promotionen
- Ingo Rieping: Communication in Parallel Systems - Models, Algorithms and Implementations, 14.11.2000
- Matthias Westermann: Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints, 03.11.2000
- Klaus Schröder: Balls into Bins: A Paradigm for Job Allocation, Data Distribution Processes, and Routing, 12.05.2000
Habilitationen
- Christian Scheideler: Probabilistische Methoden für Koordinierungsprobleme, 30.06.2000
Promotionen
- Tamas Lukovszki: New Results on Geometric Spanners and Their Applications, 01.10.1999
Habilitationen
- Artur Czumaj: Randomization and Approximation Techniques for some Combinatorial Problems, 22.12.1999
Promotionen
- Berthold Vöcking: Static and Dynamic Data Management Networks, 18.12.1998
- Brigitte Oesterdiekhoff: On Periodic Comparator Networks, 15.05.1998
Promotionen
- Willy-Bernhard Strothmann: Bounded Degree Spanning Trees, 19.12.1997
- Wolfgang Dittrich: Communication and I/O Efficient Parallel Data Structures, 22.08.1997
- Armin Bäumker: Communication Efficient Parallel Searching, 19.09.1997
Promotionen
- Christian Scheideler: Universal Routing Strategies for Interconnection Networks, 18.12.1996
Promotionen
- Foued Ameur: Space-Bounded Learning Algorithms, 20.12.1995
- Alf Wachsmann: Eine Bibliothek von Basisdiensten für Parallelrechner: Routing, Synchronisation, gemeinsamer Speicher, 08.09.1995
- Artur Czumaj: Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations, 30.08.1995
- Volker Stemann: Contention Resolution in Hashing Based Shared Memory Simulations, 06.07.1995
Promotionen
- Rolf Wanka: Paralleles Sortieren auf mehrdimensionalen Gittern, 16.09.1994
Habilitationen
- Martin Dietzfelbinger: Universal hashing in sequential, parallel, and distributed computing, 12.1992