Bibliography

1

K. Mehlhorn.
On the size of sets of computable functions.
In Proceedings of the 14th IEEE Symposium on Automata and Switching Theory, pages 190-196, 1973.

2

K. Mehlhorn.
The `almost all' theory of subrecursive degrees is decidable.
In Proceedings of the 2nd International Colloquium of Automata, Languages and Programming (ICALP'74), volume 14 of Lecture Notes in Computer Science, pages 317-325. Springer, 1974.

3

K. Mehlhorn.
Nearly optimal binary search trees.
Acta Informatica, 5:287-295, 1975.

4

H. Alt and K. Mehlhorn.
Lower bounds on the space complexity of context-free recognition.
In Proceedings of the 3rd International Colloquium on Automata, Languages and Progr amming (ICALP'76), pages 338-354. Edinburgh University Press, 1976.

5

K. Mehlhorn.
Bracket languages are recognizable in logarithmic space.
Information Processing Letters, 5(6):168-170, 1976.

6

K. Mehlhorn.
On the complexity of monotone realizations of matrix multiplication.
Computing, 16:99-111, 1976.

7

K. Mehlhorn.
Polynomial and abstract subrecursive classes.
Journal of Computer and System Sciences, 12:147-178, 1976.

8

K. Mehlhorn.
An improved lower bound on the formula complexity of context-free recognition.
EIK, 12(11/12):523-524, 1976.

9

P. Deussen and K. Mehlhorn.
Van Wijngarden grammars and EXSPACE.
Acta Informatica, 8(2):193-199, 1977.

10

K. Mehlhorn.
Best possible bounds on the weighted path length of optimal binary search trees.
SIAM Journal of Computing, 6(2):235-239, 1977.

11

K. Mehlhorn.
Effiziente Algorithmen: Ein Beispiel.
Informatik-Spektrum, 1:81-89, 1978.

12

K. Mehlhorn and M. Tsagarakis.
On the isomorphism of two algorithms: Hu/Tucker and Garsia/Wachs.
In Colloque de Lille `Les Arbres en Algebre et en Programmation', 1979.

13

H. Alt and K. Mehlhorn.
Complexity arguments in algebraic language theory.
RAIRO Theor. Inform., 13(3):217-225, 1979.

14

K. Mehlhorn.
Parsing marco-grammars top-down.
Information & Control, 40(2):123-143, 1979.

15

K. Mehlhorn.
Some remarks on boolean sums.
Acta Informatica, 12:371-375, 1979.

16

K. Mehlhorn.
Dynamic binary search.
SIAM Journal of Computing, 8(2):175-198, 1979.

17

K. Mehlhorn.
Dynamic data structures.
Mathematical Centre Tracts, 108:71-79, 1979.

18

K. Mehlhorn.
Sorting presorted files.
In Proceedings of the 4th GI-Conference on Theoretical Computer Science, volume 67 of Lecture Notes in Computer Science, pages 199-212. Springer, 1979.

19

K. Mehlhorn.
Searching, sorting, and information theory.
In Proceedings of the Mathematical Foundations of Computer Science (MFCS'79), volume 74 of Lecture Notes in Computer Science, pages 67-78. Springer, 1979.

20

K. Mehlhorn.
Aspekte der Komplexitätstheorie illustriert am Beispiel des Sortierens.
In Proceedings of the GI-Jahrestagung 1979, volume 19, pages 16-23, 1979.
Informatik-Fachberichte.

21

D. Altenkamp and K. Mehlhorn.
Codes: Unequal letter costs, unequal probabilities.
Journal of the ACM, 27(3):412-427, 1980.

22

N. Blum and K. Mehlhorn.
On the average number of rebalancing steps in weight-balanced trees.
Theoretical Computer Science, 11:303-320, 1980.

23

R. Güttler, K. Mehlhorn, and W. Schneider.
Binary search trees: Average and worst case behaviour.
EIK, 1-3:42-61, 1980.

24

K. Mehlhorn.
An efficient algorithm for the construction of nearly optimal prefix codes.
IEEE Transaction on Information Theory, IT-26(5):513-517, 1980.

25

K. Mehlhorn.
Arbitrary weight changes in dynamic trees.
RAIRO Theor. Inform., 15(3):183-211, 1981.

26

K. Mehlhorn.
A lower bound on the efficiency of static to dynamic transforms of data structures.
Math. Systems Theory, 15:1-16, 1981.

27

K. Mehlhorn and M. Overmars.
Optimal dynamization of decomposable searching problems.
Information Processing Letters, 12(2):93-98, 1981.

28

S. Huddleston and K. Mehlhorn.
Robust balancing in B-trees.
In Proceedings of the 5th GI-Conference on Theoretical Computer Science, volume 104 of Lecture Notes in Computer Science, pages 234-244. Springer, 1981.

29

T. Lengauer and K. Mehlhorn.
Four results on the complexity of VLSI computation.
Advances in Computing Research, 2:1-22, 1984.

30

K. Mehlhorn.
A partial analysis of height-balanced trees under random insertions and deletions.
SIAM Journal of Computing, 11(4):748-760, 1982.

31

K. Mehlhorn.
A new representation for linear lists.
Acta Informatica, 17:157-184, 1982.

32

K. Mehlhorn and E.M. Schmidt.
Las Vegas is better than determinism in VLSI and distributed computing.
In Proceedings of the 14th Annual ACM SIGACT Symposiumon Theory of Computing (STOC'82), 1982.

33

K. Mehlhorn.
On the program size of perfect and universal hash functions.
In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS'82), pages 170-175, 1982.

34

M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninnke, W. Keber, K. Mehlhorn, S. Näher, H. Rohnert, and T. Winter.
A probabilistic algorithm for vertex connectivity of graphs.
Information Processing Letters, 15(3):135-136, 1982.

35

B. Eisenbarth, N. Ziviani, G.H. Gonnet, K. Mehlhorn, and D. Wood.
The theory of fringe analysis and its application to 2-3 trees and B-trees.
Information & Control, 55:25-174, 1982.

36

J.-W. Hong, K. Mehlhorn, and A. Rosenberg.
Cost tradeoffs in graph embeddings with applications.
Journal of the ACM, 30(4):709-728, 1983.

37

K. Mehlhorn and B.H. Schmidt.
A single source shortest path algorithm for graphs with separators.
In Proceedings of the Fundamentals of Computation Theory (FCT'83), volume 158 of Lecture Notes in Computer Science, pages 302-309. Springer, 1983.

38

B.v. Braunmühl, S. Cook, K. Mehlhorn, and R. Verbeek.
Optimal algorithms for deterministic context-free recognition.
Information & Control, 56:34-51, 1983.

39

K. Mehlhorn and F.P. Preparata.
AT²-optimal VLSI multipliers with minimum computation time.
Information & Control, 58:137-196, 1983.

40

K. Mehlhorn and U. Vishkin.
Granularity of memory in parallel computation.
Acta Informatica, 21:339-374, 1984.

41

H. Alt, K. Mehlhorn, and J. Munro.
On the complexity of partial match retrieval.
Information Processing Letters, 19(2):61-65, 1984.

42

S. Hertel, M. Mäntylä, K. Mehlhorn, and J. Nievergelt.
Space sweep solves intersection of two convex polyhedra elegantly.
Acta Informatica, 21:501-519, 1984.

43

T. Lengauer and K. Mehlhorn.
The HILL system: A design environment for the hierarchical spezification, compaction, and simulation of integrated circuit layouts.
In Paul Penfield Ir., editor, Proceedings of the MIT VLSI Conference, pages 139-149. Artech House, Inc., 1984.

44

K. Mehlhorn.
AT² optimal VLSI integer division and integer square rooting.
Integration, the VLSI Journal, 2:164-167, 1984.

45

H. Mannila and K. Mehlhorn.
A fast algorithm for renaming a set of clauses as a Horn set.
Information Processing Letters, 21(5):269-272, 1985.

46

H. Alt and K. Mehlhorn.
Searching semi-sorted tables.
SIAM Journal of Computing, 14(4):840-848, 1985.

47

O. Fries, K. Mehlhorn, and S. Näher.
Dynamization of geometric data structures.
In Proceedings of the ACM Conference on Computational Geometry, pages 168-176, 1985.

48

K. Mehlhorn and K. Simon.
Intersecting two polyhedra one of which is convex.
In Proceedings of Fundamentals of Computation Theory (FCT'85), volume 199 of Lecture Notes in Computer Science, pages 534-542. Springer, 1985.

49

K. Mehlhorn and A. Tsakalidis.
Dynamic interpolation search.
In Proceedings of the 12th International Conference on Automata, Languages and Programming (ICALP'85), volume 194 of Lecture Notes in Computer Science, pages 424-434. Springer, 1985.

50

S. Hertel and K. Mehlhorn.
Fast triangulation of the plane with respect to simple polygons.
Information & Control, 64(1-3), 1985.

51

K. Mehlhorn and F.P. Preparata.
Routing through a rectangle.
Journal of the ACM, 33(1):60-85, 1986.

52

K. Mehlhorn and S. Näher.
Dynamic fractional cascading.
Algorithmica, 5:215-241, 1990.

53

M. Becker and K. Mehlhorn.
Algorithms for routing in planar graphs.
Acta Informatica, 23:163-176, 1986.

54

M. Kaufmann and K. Mehlhorn.
Routing through a generalized switchbox.
Journal of Algorithms, 7:510-531, 1986.

55

K. Mehlhorn and A. Tsakalidis.
An amortized analysis of insertions into AVL-trees.
SIAM Journal of Computing, 15(1):22-33, 1986.

56

K. Mehlhorn, F.P. Preparata, and M. Sarrafzadeh.
Channel routing in knock-knee mode: Simplified algorithms and proofs.
Algorithmica, 1:213-221, 1986.

57

K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R.E. Tarjan.
Sorting Jordan sequences in linear time using level-linked search trees.
Information & Control, 68(1-3):170-184, 1986.

58

M. Fürer and K. Mehlhorn.
AT²-optimal Galois field multiplier for VLSI.
IEEE Transactions on Computers, 38(9):1333-1336, 1989.

59

K. Mehlhorn.
Über Verdrahtungsalgorithmen.
Informatik-Spektrum, 9:227-234, 1986.

60

K. Mehlhorn and B.H. Schmidt.
On BF-orderable graphs.
Discrete Applied Mathematics, 15:315-327, 1986.

61

H. Jung and K. Mehlhorn.
Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees.
Information Processing Letters, 27(5):227-236, 1988.

62

T. Lengauer and K. Mehlhorn.
VLSI complexity, efficient VLSI algorithms and the HILL design system.
In C. Trullemans, editor, Algorithmics in VLSI, International Lecture Series in Computer Science, pages 33-89, 1987.

63

O. Fries, K. Mehlhorn, S. Näher, and A. Tsakalidis.
A $\hbox{\ log\ log\ }n$ data structure for three-sided range queries.
Information Processing Letters, 25(4):269-273, 1987.

64

K. Mehlhorn, S. Näher, and H. Alt.
A lower bound on the complexity of the union-split-find problem.
SIAM Journal of Computing, 17(6):1093-1102, 1988.

65

K. Mehlhorn and F. Preparata.
AT²-optimal integer division with computation time $\Omega$(log $n^{1+\epsilon}$).
Information and Computation, 72:270-282, 1987.

66

H. Alt, T. Hagerup, K. Mehlhorn, and F. Preparata.
Deterministic simulation of idealized parallel computers on more realistic ones.
SIAM Journal of Computing, 16(4):808-835, 1987.

67

H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl.
Congruence, similarity, and symmetries of geometric objects.
Journal of Discrete and Computational Geometry, 3:237-256, 1988.

68

K. Mehlhorn and S. Näher.
Compaction with automatic jog insertion.
IEEE Transactions on CAD of Integrated Circuits and Systems, 9(2):158-166, 1990.

69

K. Mehlhorn.
A faster approximation algorithm for the Steiner problem in graphs.
Information Processing Letters, 27(2):125-128, 1988.

70

R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan.
Faster algorithms for the shortest path problem.
Journal of the ACM, 3(2):213-223, 1990.

71

K. Mehlhorn and C.K. Yap.
Constructive Whitney-Graustein theorem: Or how to untangle closed planar curves.
SIAM Journal of Computing, 20(4):603-621, 1991.

72

K. Mehlhorn and W. Rülling.
Compaction on the torus.
IEEE Transactions on CAD of Integrated Circuits and Systems, 9(4):389-397, 1990.

73

S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. Rülling, and C. Storb.
On continuous homotopic one layer routing.
In ACM Geometry Conference 88, pages 392-402, 1988.

74

M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM Journal of Computing, 23(4):738-761, 1994.

75

K. Mehlhorn, W.J. Paul, and C. Uhrig.
K versus k+1 index registers and modifiable versus non-modifiable programs.
Information and Computation, 101:123-129, 1992.

76

Y.T. Ching, K. Mehlhorn, and M. Smid.
Dynamic deferred data structuring.
Information Processing Letters, 35:37-40, 1990.

77

M. Kaufmann and K. Mehlhorn.
A linear-time algorithm for the homotopic routing problem in grid graphs.
SIAM Journal of Computing, 23(2):227-246, 1994.

78

M. Kaufmann and K. Mehlhorn.
Routing problems in grid graphs.
In L. Korte and S. Prömel, editors, Paths, Flows, and VLSI Layout, volume 9, chapter Algorithms and Combinatorics. Springer, 1990.

79

K. Mehlhorn, C. O'Dúnlaing, and S. Meiser.
On the construction of abstract Voronoi diagrams.
Discrete and Computational Geometry, 6(3):211-224, 1991.

80

K. Mehlhorn, S. Näher, and M. Rauch.
On the complexity of a game related to the dictionary problem.
SIAM Journal of Computing, 19(5):902-906, 1990.

81

K. Mehlhorn and S. Näher.
LEDA: A library of efficient data types and algorithms.
In Antoni Kreczmar and Grazyna Mirkowska, editors, Proceedings of the 14th International Symposium on Mathematical Foundations of Computer Science (MFCS'89), volume 379 of Lecture Notes in Computer Science, pages 88-106. Springer, 1989.

82

J. Cheriyan, T. Hagerup, and K. Mehlhorn.
Can a maximum flow be computed in o(nm) time?
In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP'90), volume 443 of Lecture Notes in Computer Science, pages 235-248. Springer, 1990.

83

K. Mehlhorn and A. Tsakalidis.
Data structures.
In Handbook of Theoretical Computer Science, pages 303-341. Elsevier Science Publishers, 1990.

84

R. Fleischer, H. Jung, and K. Mehlhorn.
A communication-randomness tradeoff for two-processor systems.
Information and Computation, 116(2):155-161, 1995.

85

R. Fleischer, K. Mehlhorn, G. Rote, E. Welzl, and C. Yap.
Simultaneous inner and outer approximation of shapes.
Algorithmica, 8(5/6):365-389, 1992.

86

H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig.
Approximate motion planning and the complexity of the boundary of the union of simple geometric figures.
Algorithmica, 8(5/6):391-406, 1992.

87

K. Mehlhorn, S. Näher, and C. Uhrig.
Hidden line elimination for isooriented rectangles.
Information Processing Letters, 35:137-143, 1990.

88

K. Mehlhorn and S. Näher.
Bounded ordered dictionaries in $O(\log \log N)$ time and O(n) space.
Information Processing Letters, 35:183-189, 1990.

89

H. Alt, N. Blum, K. Mehlhorn, and M. Paul.
Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}\sqrt{m/\log n})$.
Information Processing Letters, 37:237-240, 1991.

90

K. Mehlhorn, M. Sharir, and E. Welzl.
Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection.
Computational Geometry: Theory and Applications, 3:235-246, 1993.

91

K. Clarkson, K. Mehlhorn, and R. Seidel.
Four results on randomized incremental constructions.
Computational Geometry: Theory and Applications, 3:185-212, 1993.

92

Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn.
Dynamic point location in general subdivisions.
Journal of Algorithms, 17(3):342-380, 1994.

93

H. Alt, V. Geffert, and K. Mehlhorn.
A lower bound for the nondeterministic space complexity of contextfree recognition.
Information Processing Letters, 42:25-27, 1992.

94

H. Alt, L. Guibas, K. Mehlhorn, R. Karp, and A. Widgerson.
A method for obtaining randomized algorithms with small tail probabilities.
Algorithmica, 16(4/5):543-547, 1996.

95

M. Kaufmann and K. Mehlhorn.
On local routing of two-terminal nets.
Journal on Combinatorial Theory B, 55:33-72, 1992.

96

K. Mehlhorn and S. Näher.
Algorithm design and software libraries: Recent developments in the LEDA project.
In IFIP Transactions: ``Algorithms, Software, Architecture'', Information Processing 92, Vol. I, pages 493-505, 1992.

97

P. Dietz, K. Mehlhorn, R. Raman, and C. Uhrig.
Lower bounds for set intersection queries.
Algorithmica, 14(2):154-168, August 1995.

98

K. Mehlhorn, S. Meiser, and R. Rasch.
Furthest site abstract voronoi diagrams.
Technical Report MPI-I-92-125, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1992.

99

L. Kucera, K. Mehlhorn, B. Preis, and E. Schwarzenecker.
Exact algorithms for a geometric packing problem (extended abstract).
In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS'93), volume 665 of Lecture Notes in Computer Science, pages 317-322. Springer, 1993.

100

T. Hagerup, K. Mehlhorn, and I. Munro.
Optimal algorithms for generating time-varying discrete random variates.
In Proceedings of International Conference on Automata, Language, and Programming (ICALP'93), volume 700 of Lecture Notes in Computer Science, pages 253-264. Springer, 1993.

101

K. Mehlhorn, R. Sundar, and C. Uhrig.
Maintaining dynamic sequences under equality tests in polylogarithmic time.
Algorithmica, 17(2):183-198, 1997.

102

R. Klein, K. Mehlhorn, and S. Meiser.
Randomized incremental construction of abstract Voronoi diagrams.
Computational Geometry: Theory and Applications, 3:157-184, 1993.

103

D. Dubhashi, K. Mehlhorn, D. Ranjan, and C. Thiel.
Searching, sorting, and randomized algorithms for central elements and ideal counting in posets.
In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'93), volume 761 of Lecture Notes in Computer Science, pages 436-443. Springer, 1993.

104

K. Dobrindt, K. Mehlhorn, and M. Yvinec.
A complete and efficient algorithm for the intersection of a general and a convex polyhedron.
In Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro, and Sue Whitesides, editors, Proceedings of the 3rd International Workshop on Algorithms and Data Structures (WADS'93), volume 709 of Lecture Notes in Computer Science, pages 314-324, Montréal, Canada, 11-13 August 1993. Springer.

105

G. Bilardi, S. Chaudhuri, D. Dubhashi, and K. Mehlhorn.
A lower bound for area-universal graphs.
Information Processing Letters, 51(2):101-106, 1994.

106

C. Burnikel, K. Mehlhorn, and S. Schirra.
On degeneracy in geometric computations.
In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), pages 16-23, 1994.

107

K. Mehlhorn, P. Mutzel, and S. Näher.
An implementation of the Hopcroft and Tarjan planarity test and embedding algorithm.
Technical Report MPI-I-93-151, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1993.

108

K. Mehlhorn and P. Mutzel.
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm.
Algorithmica, 16(2):233-242, 1995.

109

K. Mehlhorn and S. Näher.
The implementation of geometric algorithms.
In IFIP Transactions A-51, ``Technology and Foundations'', Information Processing`94, Vol. I, pages 223-231, 1994.

110

C. Burnikel, K. Mehlhorn, and S. Schirra.
How to compute the Voronoi diagram of line segments: Theoretical and experimental results.
In Springer, editor, Proceedings of the 2nd Annual European Symposium on Algorithms - ESA'94, volume 855 of Lecture Notes in Computer Science, pages 227-239, 1994.

111

K. Mehlhorn and V. Priebe.
On the all-pairs shortest path algorithm of Moffat and Takaoka.
In Proceedings of the 3rd Annual European Symposium (ESA'95), volume 979 of Lecture Notes in Computer Science, pages 185-198. Springer, 1995.

112

K. Mehlhorn.
Experiences with the implementation of geometric algorithms.
In Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, and Nicola Santoro, editors, Proceedings of the 4th International Workshop on Algorithms and Data Structures (WADS'95), volume 955 of Lecture Notes in Computer Science, pages 518-518. Springer, August 1995.

113

K. Mehlhorn and S. Näher.
LEDA: A platform for combinatorial and geometric computing.
Communications of the ACM, 38(1):96-102, 1995.

114

C. Burnikel, J. Könemann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig.
Exact geometric computation in LEDA.
In Proceedings of the 11th Annual Symposium on Computational Geometry (SCG'95), pages C18-C19, New York, NY, USA, June 1995. ACM Press.

115

Kurt Mehlhorn, Stefan Näher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, and Christian Uhrig.
Checking geometric programs or verification of geometric structures.
Computational Geometry, 12(1-2):85-103, 1999.

116

J. Cheriyan, T. Hagerup, and K. Mehlhorn.
An o(n³)-time maximum flow algorithm.
SIAM Journal of Computing, 25(6):1144-1170, 1996.

117

S. Arya, M.J. Golin, and K. Mehlhorn.
On the Expected Depth of Random Circuits.
Combinatorics, Probability, and Computing, 8:209-228, 1999.

118

J. Cheriyan and K. Mehlhorn.
Algorithms for dense graphs and networks on the random access computer.
Algorithmica, 15(6):521-549, 1996.

119

U. Finkler and K. Mehlhorn.
Runtime prediction of real programs on real machines.
In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), pages 380-389, 1997.

120

K. Mehlhorn and V. Priebe.
On the all-pairs shortes path algorithm of Moffat and Takaoka.
Random Structures &Algorithms, 10:205-220, 1997.

121

K. Reinert, H.-P. Lenhof, P. Mutzel, K. Mehlhorn, and J.D. Kececioglu.
A branch-and-cut algorithm for multiple sequence alignment.
In Proceedings of the First International Conference on Computational Molecular Biology, pages 241-250, New York, January19-22 1997. ACM Press.

122

K. Mehlhorn, T.C Shermer, and C.K. Yap.
A complete roundness classification procedure.
In Proceedings of the 13th Annual ACM Symposium on Computational Geometry (SCG'97), pages 129-138, 1997.

123

C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
A strong and easily computable separation bound for arithmetic expressions involving square roots.
In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 97), pages 702-709, 1997.

124

C. Cooper, A. Frieze, K. Mehlhorn, and V. Priebe.
Average-case complexity of shortest-paths problems in the vertex-potential model.
In José Rolim, editor, Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM`97), volume 1269 of Lecture Notes in Computer Science, pages 15-26. Springer, 1997.
full papeer to appear in ``Random Structures and Algorithms''.

125

A. Crauser, K. Mehlhorn, and U. Meyer.
Kürzeste-Wege-Berechnung bei sehr großen Datenmengen.
Promotion tut not: Innovationsmotor ``Graduiertenkolleg", Aachener Beiträge, pages 113-132, 1997.

126

E. Althaus and K. Mehlhorn.
Maximum network flow with floating point arithmetic.
Information Processing Letters, 66:109-113, 1998.

127

A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E.A. Ramos.
Randomized external-memory algorithms for some geometric problems.
In Proceedings of the 14th Annual ACM Symposium on Computational Geometry (SCG'98), 1998.

128

K. Mehlhorn and S. Näher.
From algorithms to working programs: On the use of program checking in LEDA.
Lecture Notes in Computer Science, 1450:84-??, 1998.

129

C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
Exact efficient computational geometry made easy.
In Proceedings of the 15th Annual Symposium on Computational Geometry (SCG'99), 1999.
www.mpi-sb.mpg.de/ mehlhorn/ftp/egcme.ps.

130

A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders.
A parallelization of Dijkstra's shortest path algorithm.
Lecture Notes in Computer Science, 1450:722-??, 1998.

131

K. Mehlhorn, M. Müller, S. Näher, S. S. Schirra, M. Seel, C. Uhrig, and J. Ziegler.
A computational basis for higher-dimensional computational geometry and its applications.
Computational Geometry: Theory and Applications, 10:289-303, 1998.
www.mpi-sb.mpg.de/ seel.

132

A. Crauser and K. Mehlhorn.
LEDA-SM, extending LEDA to secondary memory.
In Workshop on Algorithm Engineering 1999, LNCS, 1999.
www.mpi-sb.mpg.de/ mehlhorn/ftp/LEDA-SM.ps.

133

T.K. Dey, K. Mehlhorn, and E.A. Ramos.
Curve reconstruction: Connecting dots with good reason.
In Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG'99), pages 197-206, 1999.
www.mpi-sb.mpg.de/ mehlhorn/ftp/cure.ps.

134

J. Cheriyan and K. Mehlhorn.
An analysis of the highest-level selection rule in the preflow-push max-flow algorithm.
IPL, 69:239-242, 1999.
www.mpi-sb.mpg.de/ mehlhorn/ftp/maxflow.ps.

135

S. Arikati and K. Mehlhorn.
A correctness certificate for the Stoer-Wagner mincut algorithm.
Information Processing Letters, 70:251-254, 1999.
www.mpi-sb.mpg.de/ mehlhorn/ftp/mincut.ps.

136

E. Althaus and K. Mehlhorn.
Polynomial time TSP-based curve reconstruction.
accepted for SODA 2000, www.mpi-sb.mpg.de/ mehlhorn/ftp/TSP-curve.ps, 1999.

137

E. Althaus, K. Mehlhorn, S. Näher, and S. Schirra.
Experiments on curve reconstruction.
unpublished, www.mpi-sb.mpg.de/ mehlhorn/ftp/exp-curve.ps, 1999.