Prof. Dr. Ulrich Meyer
Prof. Dr. Ulrich Meyer
Institute for Computer Science
Robert-Mayer-Straße 11-15
60325 Frankfurt am Main
Room 304
Tel: +49-69-798-28433
Fax: +49-69-798-28357
Email: umeyer@ae.cs.uni-frankfurt.de
Research Interests
Research on graph algorithms, randomized and deterministical, on different models of computations: RAM, PRAM, Distributed Memory, External Memory. Check out the research section for more information.
In my PhD thesis I mainly focused on the average-case analysis of the single-source shortest-path problem on RAM and PRAM.
Program Committees
Publications
70
R. Jacob, U. Meyer, and L. Toma
List Ranking
In Encyclopedia of Algorithms, Springer 2016, to appear
69
U. Meyer, and N. Zeh
I/O-Model
In Encyclopedia of Algorithms, Springer 2016, to appear
68
S.Ashkiani, A. Davidson, U. Meyer, and J. Owens
GPU Multisplit
In Proc. 21st Symposium on Principles and Practice of Parallel Programming (PPoPP), ACM, 2016 to appear
67
Ulrich Meyer, Manuel Penschuck
Generating Massive Scale-Free Networks under Resource Constraints
In: Proc. 18th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2016
66
A. Kovacs, U. Meyer, G. Moruz, and A. Negoescu
The optimal structure of algorithms for alpha-paging
In Information Processing Letters, 115(12):932-938, 2015
65
P. Wollstadt, U. Meyer, and M. Wibral
A Graph Algorithmic Approach to Separate Direct from Indirect Neural Interactions
In PLoS ONE 10(10):e0140530, 2015
64
Annamaria Kovacs, Ulrich Meyer, and Carmine Ventre
Mechanisms with monitoring for truthful RAM allocation
In: Web and Internet Economics - 11th International Conference, WINE 2015, Amsterdam, The Netherlands, 2015
63
Deepak Ajwani, Ulrich Meyer, David Veith
An I/O-efficient Distance Oracle for Evolving Real-World Graphs
In: Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX), San Diego, USA, 2015.
62
Catherine C. McGeoch and Ulrich Meyer
2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014
SIAM
61
Ulrich Meyer, Volker Weichert
Algorithm Engineering für moderne Hardware
Informatik Spektrum 36(2), 2013, 153-161
60
Andreas Beckmann, Ulrich Meyer, David Veith
An Implementation of I/O-Efficient Dynamic Breadth-First Search Using Level-Aligned Hierarchical Clustering
In: Proc: Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013, 121-132
59
M. Wibral, P. Wollstadt, U. Meyer, N.Pampu, V. Priesemann, and R. Vicente
Revisiting Wieners's principle of causality - interaction-delay reconstruction using trasfer entropy, and multivariate analysis on delay-weighted graphs.
In: Proc. 4th Int. Conf. of the IEEE EMBS (EMBC), 2012
58
Ulrich Meyer, Norbert Zeh
I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths
ACM Transactions on Algorithms 8 (3): 22, 2012
57
Deepak Ajwani, Andreas Beckmann, Ulrich Meyer, David Veith
I/O-efficient approximation of graph diameters by parallel cluster growing - a first experimental study
ARCS 2012 Workshops, 28. Februar - 2. März 2012, München, Germany, 493-504
56
Deepak Ajwani, Ulrich Meyer, David Veith
I/O-efficient Hierarchical Diameter Approximation
In: Proc. Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012, 72-83
55
Andreas Beckmann, Jaroslaw Fedorowicz, Jörg Keller, Ulrich Meyer
A structural analysis of the A5/1 state transition graph
In: Proceedings First Workshop on GRAPH Inspection and Traversal Engineering, GRAPHITE 2012, Tallinn, Estonia, 1st April 2012, 5-19
54
Ulrich Meyer, Andrei Negoescu, Volker Weichert
New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches
In: Proc. Theory and Practice of Algorithms in (Computer) Systems, First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, 217-228
53
M. de Berg, and U. Meyer
Algorithms
ESA 2010, 18th Annual European Symposium, Part I, volume 6346 of LNCS. Springer 2010
52
M. de Berg, and U. Meyer
Algorithms
ESA 2010, 18th Annual European Symposium, Part II, volume 6347 of LNCS. Springer 2010
51
Andreas Beckmann, Ulrich Meyer, Peter Sanders, and Johannes Singler
Energy-Efficient Sorting using Solid State Disks
In: Proc. 1st International Green Computing Conference (IGCC 2010), Chicago, USA, 2010, 191-202
50
U. Meyer
Via Detours to I/O-Efficient Shortest Paths
In: Efficient Algorithms, volume 5760 of LNCS, pages 219-232. Springer, 2009
49
D. Ajwani, R. Dementiev, U. Meyer, and V. Osipov
Breadth first search on massive graphs.
In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Pages 291-308. AMS Press, 2009
48
A. Kovacs, U. Meyer, G. Moruz, and A.Negoescu
Online Paging for Flash Memory Devices
In: Proc. 20th Int. Symposium on Algorithms and Computation (ISAAC), volume 5878 of LNCS, pages 352-361. Springer 2009
47
Deepak Ajwani, Andreas Beckmann, Riko Jacob, Ulrich Meyer, and Gabriel Moruz
On Computational Models for Flash Memory Devices
In: Proc. 8th International Symposium Experimental Algorithms (SEA 2009), Dortmund, Germany, 2009, 16-27
46
Deepak Ajwani and Ulrich Meyer
Design and Engineering of External Memory Traversal Algorithms for General Graphs
In: Algorithmics of Large and Complex Networks, LNCS, Springer, 2009
45
Ulrich Meyer and Vitaly Osipov
Design and Implementation of a Practical I/O-efficient Shortest Paths Algorithm
In: Proc. 11th Workshop on Algorithm Engineering and Experiments (ALENEX), New York, USA, 2009
44
D. Ajwani, T. Friedrich, and U. Meyer
An O(n^2.75) algorithm for incremental topological ordering
ACM Transactions on Algorithms, 4(4), 2008
43
Deepak Ajwani, Itay Malinger, Ulrich Meyer, and Sivan Toledo
Characterizing the Performance of Flash Memory Storage Devices and Its Impact on Algorithm Design
In: Proc. 7th Intern. Workshop on Experimental Algorithms (WEA), Provincetown, USA, 2008, 208-219
42
Ulrich Meyer
On Dynamic Breadth-First Search in External-Memory
In: Proc. 25th Annual Symposium on Theoretical Aspects (STACS), Bordeaux, France, 2008, 551-560
41
Ulrich Meyer
On Trade-Offs in External-Memory Diameter Approximation
In: Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT), Gothenburg, Sweden, 2008
40
Deepak Ajwani, Ulrich Meyer, and Vitaly Osipov
Improved external memory BFS implementation
In: 9th Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, USA, 2007, 3-12
39
Deepak Ajwani, Roman Dementiev, and Ulrich Meyer
A computational study of external memory BFS algorithms
In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 06, Miami, USA, 2006, 601-610
38
Stefan Funke, Alexander Kesselman, Ulrich Meyer, and Michael Segal
A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs
ACM Transactions on Sensor Networks 2 (3): 444-453, 2006
37
Debora Donato, Luigi Laura, Stefano Leonardi, Stefano Millozzi, Ulrich Meyer, and Jop F. Sibeyn
Algorithms and Experiments for the Webgraph
Journal of Graph Algorithms and Applications 10 (2): 219-236, 2006
36
Deepak Ajwani, Tobias Friedrich, and Ulrich Meyer
An O(n2.75) algorithm for online topological ordering
In: Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, 2006, 53-64
35
Ulrich Meyer and Norbert Zeh
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
In: Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, 2006, 540-551
34
Stefan Funke, Alexander Kesselman, Ulrich Meyer, and Michael Segal
A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs
In: 1st IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2005), Montreal, Canada, 2005, 220-223
33
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh
Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths
In: Algorithm theory, SWAT 2004 : 9th Scandinavian Workshop on Algorithm Theory ; Humlebæk, Denmark, July 8-10, 2004 ; proceedings, Humlebaek, Denmark, 2004, 480-492
32
Lars Arge, Ulrich Meyer, and Laura Toma
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
In: Automata, languages and programming : 31st International Colloquium, ICALP 2004, Turku, Finland, 2004, 146-157
31
U. Meyer, P. Sanders, and J.F.Sibeyn
Algorithms for Memory Hierarchies
volume 5760 of LNCS, Springer, 2004
30
Ulrich Meyer and Peter Sanders
[Delta]-stepping: a parallelizable shortest path algorithm
Journal of Algorithms 49: 114-152, 2003
29
Luigi Laura, Stefano Leonardi, Stefano Millozzi, Ulrich Meyer, and Jop F. Sibeyn
Algorithms and Experiments for the Webgraph
In: Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, September, 16 - September, 19, 2003, 703-714
28
Ulrich Meyer
Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
Journal of Algorithms 48: 91-134, 2003
27
Irit Katriel and Ulrich Meyer
Elementary Graph Algorithms in External Memory
In: Algorithms for Memory Hierarchies, 2003, 62-84
26
Lars Arge, Ulrich Meyer, Laura Toma, and Norbert Zeh
On external-memory planar depth first search
Journal of Graph Algorithms and Applications 7 (2): 105-129, 2003
25
Ulrich Meyer and Norbert Zeh
I/O-Efficient Undirected Shortest Paths
In: Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, September, 16 - September, 19, 2003, 434-445
24
Ulrich Meyer
Buckets Strike Back: Improved Parallel Shortest-Paths
In: International Parallel and Distributed Processing Symposium (IPDPS-02), Fort Lauderdale, USA, 2002, 75-75.
23
Ulrich Meyer
Design and Analysis of Sequential and Parallel Single-Source Shortest-Paths Algorithms
PhD thesis, Universität des Saarlandes, 2002
22
Kurt Mehlhorn and Ulrich Meyer
External-Memory Breadth-First Search with Sublinear I/O
In: Algorithms - ESA 2002 : 10th Annual European Symposium, Rome, Italy, 2002, 723-735
21
Jop F. Sibeyn, James Abello, and Ulrich Meyer
Heuristics for Semi-External Depth First Search on Directed Graphs
In: SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, Winnipeg, Canada, 2002, 282-292
20
Ulrich Meyer and Jop F. Sibeyn
Oblivious Gossiping on Tori
Journal of Algorithms 42 (1): 1-19, 2002
19
Andreas Crauser, Ulrich Meyer, and Klaus Brengel
An experimental study of priority queues in external memory
ACM
18
Ulrich Meyer
External Memory BFS on Undirected Graphs with Bounded Degree
In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01), Washington, DC, January, 07-09, 2001, 87-88
17
Ulrich Meyer
Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs
In: Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01) :, Manchester, UK, August, 28 - August, 31, 2001, 343-351
16
Lars Arge, Ulrich Meyer, Laura Toma, and Norbert Zeh
On External-Memory Planar Depth First Search
In: Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS-01), Providence, Rhode Island, USA, August, 8 - August, 10, 2001, 471-482
15
Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, and Edgar A. Ramos
Randomized External-Memory Algorithms for Line Segment Intersection and Other Geometric Problems
International Journal of Computational Geometry & Applications 11 (3): 305-337, 2001.
14
Ulrich Meyer
Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time
In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01), Washington, DC, January, 07-09, 2001, 797-806
13
Stefan Edelkamp and Ulrich Meyer
Theory and Practice of Time-Space Trade-Offs in Memory Limited Search
In: Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01), Wien, Österreich, September, 19 - September, 21, 2001, 169-184
12
Ulrich Meyer and Peter Sanders
Parallel Shortest Path for Arbitrary Graphs
In: Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference (Euro-Par-00), Munich, Germany, August, 29 - September, 1, 2000, 461-470
11
Klaus Brengel, Andreas Crauser, Ulrich Meyer, and Paolo Ferragina
An Experimental Study of Priority Queues in External Memory
In: Algorithm engineering (WAE-99) : 3rd International Workshop, WAE 99, London, UK, July, 19-21, 1999, 345-359
10
Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, and Edgar A. Ramos
I/O-optimal computation of segment intersections
In: Proceedings of the DIMACS Workshop on External Algorithms and Visualization, New Brunswick, New Jersey, May 20-22, 1998, 1999, 131-138
9
Ulrich Meyer and Peter Sanders
Delta-Stepping: A Parallel Single Source Shortest Path Algorithm
In: Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98), Venice, Italy, August, 24 - 26, 1998, 393-404
8
Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders
A Parallelization of Dijkstra's Shortest Path Algorithm
In: Proceedings of the 23rd International Symposium on the Mathematical Foundations of Computer Science (MFCS-98), Brno, Czech Republic, August, 24 - August, 28, 1998, 722-731
7
Ulrich Meyer and Jop F. Sibeyn
Gossiping Large Packets on Full-Port Tori
In: Proceedings of the 4th International Euro-Par Conference (Euro-Par-98), Southampton, United Kingdom, September, 1 - September, 4, 1998, 1040-1046
6
Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, and Edgar A. Ramos
Randomized External-Memory Algorithms for some Geometric Problems
In: Proceedings of the 14th International Annual ACM Symposium on Computational Geometry (SCG-98), Minneapolis, Minnesota, June 7-10, 1998, 259-268
5
Michael Kaufmann, Ulrich Meyer, and Jop F. Sibeyn
Matrix Transpose on Meshes: Theory and Practice
Computers and Artificial Intelligence 16 (2): 107-140, 1997
4
Michael Kaufmann, Ulrich Meyer, and Jop F. Sibeyn
Matrix Transpose on Meshes: Theory and Practice
In: Proceedings of the 11th International Parallel Processing Symposium (IPPS-97), Geneva, Switzerland, April, 1-5, 1997, 315-319
3
Michael Kaufmann, Ulrich Meyer, and Jop F. Sibeyn
Towards Practical Permutation Routing on Meshes
In: Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, October, 26-29, 1994, 656-663
2
Ulrich Meyer
Deterministische Simulation einer PRAM auf Gitterrechnern
Masters thesis, Universität des Saarlandes, 1995
1
Ulrich Meyer and Jop F. Sibeyn
Simulating the Simulator: Deterministic PRAM Simulation on a Mesh Simulator
In: Eurosim 95, Vienna, Austria, September, 11 - September, 15, 1995, 285-290