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@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
48
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
BibTeX - DOI
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
BibTeX - DOI
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, to appear
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
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
BibTeX - EE
43
Ulrich Meyer
On Dynamic Breadth-First Search in External-Memory
In: Proc. 25th Annual Symposium on Theoretical Aspects (STACS), Bordeaux, France, 2008, 551-560
BibTeX - EE
42
Ulrich Meyer
On Trade-Offs in External-Memory Diameter Approximation
In: Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT), Gothenburg, Sweden, 2008
BibTeX - EE
41
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
BibTeX - EE
40
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
BibTeX - EE
39
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
BibTeX - EE
38
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
BibTeX - EE
37
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
BibTeX - EE
36
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
BibTeX - EE
35
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
BibTeX - EE
34
Kurt Mehlhorn, Arno Eigenwillig, Kanela Kaligosi, Dieter Kratsch, Ross McConnell, Ulrich Meyer, and Jeremy P. Spinrad
Certifying Algorithms (draft)
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
BibTeX - EE
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
BibTeX - EE
31
Ulrich Meyer and Peter Sanders
[Delta]-stepping: a parallelizable shortest path algorithm
Journal of Algorithms 49: 114-152, 2003
BibTeX - EE
30
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
BibTeX - EE
29
Ulrich Meyer
Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
Journal of Algorithms 48: 91-134, 2003
BibTeX - EE
28
Irit Katriel and Ulrich Meyer
Elementary Graph Algorithms in External Memory
In: Algorithms for Memory Hierarchies, 2003, 62-84
BibTeX - EE
27
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
BibTeX - EE
26
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
BibTeX - EE
25
Ulrich Meyer
Buckets Strike Back: Improved Parallel Shortest-Paths
In: International Parallel and Distributed Processing Symposium (IPDPS-02), Fort Lauderdale, USA, 2002, 75-75.
BibTeX - EE
24
Ulrich Meyer
Design and Analysis of Sequential and Parallel Single-Source Shortest-Paths Algorithms
PhD thesis, Universität des Saarlandes, 2002
23
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
BibTeX - EE
22
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
BibTeX - EE
21
Ulrich Meyer and Jop F. Sibeyn
Oblivious Gossiping on Tori
Journal of Algorithms 42 (1): 1-19, 2002
BibTeX - EE
20
Andreas Crauser, Ulrich Meyer, and Klaus Brengel
An experimental study of priority queues in external memory
ACM
BibTeX - EE
19
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
BibTeX - EE
18
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
BibTeX - EE
17
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
BibTeX - EE
16
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.
BibTeX
15
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
BibTeX - EE
14
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
BibTeX - EE
13
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
BibTeX - EE
12
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
BibTeX - EE
11
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
10
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
BibTeX - EE
9
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
BibTeX - EE
8
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
BibTeX - EE
7
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
BibTeX - EE
6
Andreas Crauser, Kurt Mehlhorn, and Ulrich Meyer
Kürzeste-Wege-Berechnung bei sehr großen Datenmengen
In: Promotion tut not: Innovationsmotor "Graduiertenkolleg", Aachen, Germany, September, 22-23, 1997, 113-132
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
BibTeX - EE
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
BibTeX - EE
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
BibTeX