Bibliography

1

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

2

C. Aragon, R. Seidel: ``Randomized Search Trees''. Proc. 30th IEEE Symposium on Foundations of Computer Science, 540-545, 1989

3

A.V. Aho, J.E. Hopcroft, J.D. Ullman: ``Data Structures and Algorithms''. Addison-Wesley Publishing Company, 1983

4

R.K. Ahuja, T.L. Magnanti, J.B. Orlin: ``Network Flows'', Section 10.2. Prentice Hall, 1993

5

G.M. Adelson-Veslkii, Y.M. Landis: ``An Algorithm for the Organization of Information''. Doklady Akademi Nauk, Vol. 146, 263-266, 1962

6

I.J. Balaban: ``An Optimal Algorithm for Finding Segment Intersections''. Proc. of the 11th ACM Symposium on Computational Geometry, 211-219, 1995

7

J.L. Bentley: ``Decomposable Searching Problems''. Information Processing Letters, Vol. 8, 244-252, 1979

8

J.L. Bentley: ``Multi-dimensional Divide and Conquer''. CACM Vol 23, 214-229, 1980

9

R.E. Bellman: ``On a Routing Problem''. Quart. Appl. Math. 16, 87-90, 1958

10

J.L. Bentley, T. Ottmann: ``Algorithms for Reporting and Counting Geometric Intersections''. IEEE Trans. on Computers C 28, 643-647, 1979

11

R. Bayer, E. McCreight: ``Organization and Maintenance of Large Ordered Indizes'', Acta Informatica, Vol. 1, 173-189, 1972

12

N. Blum, K. Mehlhorn: ``On the Average Number of Rebalancing Operations in Weight-Balanced Trees''. Theoretical Computer Science 11, 303-320, 1980

13

C. Burnikel, K. Mehlhorn, and S. Schirra: ``How to compute the Voronoi diagram of line segments: Theoretical and experimental results''. In LNCS, volume 855, pages 227-239. Springer-Verlag Berlin/New York, 1994. Proceedings of ESA'94.

14

C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra: ``A strong and easily computable separation bound for arithmetic expressions involving square roots''. Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997.

15

C. Burnikel. ``Exact Computation of Voronoi Diagrams and Line Segment Intersections''. PhD thesis, Universität des Saarlandes, 1996.

16

T.H. Cormen, C.E. Leiserson, R.L. Rivest: ``Introduction to Algorithms''. MIT Press/McGraw-Hill Book Company, 1990

17

D. Cheriton, R.E. Tarjan: ``Finding Minimum Spanning Trees''. SIAM Journal of Computing, Vol. 5, 724-742, 1976

18

J. Cheriyan and K. Mehlhorn: ``Algorithms for Dense Graphs and Networks on the Random Access Computer''. Algorithmica, Vol. 15, No. 6, 521-549, 1996

19

O. Devillers: ``Robust and Efficient Implementation of the Delaunay Tree''. Technical Report, INRIA, 1992

20

E.W. Dijkstra: ``A Note on Two Problems in Connection With Graphs''. Num. Math., Vol. 1, 269-271, 1959

21

M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. Tarjan: ``Upper and Lower Bounds for the Dictionary Problem''. Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988

22

J.R. Driscoll, N. Sarnak, D. Sleator, R.E. Tarjan: ``Making Data Structures Persistent''. Proc. of the 18th Annual ACM Symposium on Theory of Computing, 109-121, 1986

23

J. Edmonds: ``Paths, Trees, and Flowers''. Canad. J. Math., Vol. 17, 449-467, 1965

24

H. Edelsbrunner: ``Intersection Problems in Computational Geometry''. Ph.D. thesis, TU Graz, 1982

25

J. Edmonds and R.M. Karp: ``Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems''. Journal of the ACM, Vol. 19, No. 2, 1972

26

P.v. Emde Boas, R. Kaas, E. Zijlstra: ``Design and Implementation of an Efficient Priority Queue''. Math. Systems Theory, Vol. 10, 99-127, 1977

27

A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr: ``The CGAL kernel: A basis for geometric computation''. First ACM Workshop on Applied Computational Geometry, 1996.

28

I. Fary: ``On Straight Line Representing of Planar Graphs''. Acta. Sci. Math. Vol. 11, 229-233, 1948

29

F.W. Floyd: ``Algorithm 97: Shortest Paths''. Communcication of the ACM, Vol. 5, p. 345, 1962

30

L.R. Ford, D.R. Fulkerson: ``Flows in Networks''. Princeton Univ. Press, 1963

31

S. Fortune and C. van Wyk: ``Efficient exact arithmetic for computational geometry''. Proc. of the 9th Symp. on Computational Geometry, 163-171, 1993.

32

M.L. Fredman, and R.E. Tarjan: ``Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms''. Journal of the ACM, Vol. 34, 596-615, 1987

33

H.N.Gabow: ``Implementation of algorithms for maximum matching on nonbipartite graphs''. Ph.D. thesis, Stanford Univ., Stanford, CA, 1974

34

H.N.Gabow: ``An efficient implementation of Edmond's algorithm for maximum matching on graphs''. Journal of the ACM, Vol. 23, 221-234, 1976

35

E. Gamma, R. Helm, R. Johnson, and J. Vlissides: Design patterns. Addison-Wesley Publishing Company, 1995

36

A. Goralcikova, V. Konbek: ``A Reduct and Closure Algorithm for Graphs''. Mathematical Foundations of Computer Science, LNCS 74, 301-307, 1979

37

K.E. Gorlen, S.M. Orlow, P.S. Plexico: ``Data Abstraction and Object-Oriented Programming in C++''. John Wiley & Sons, 1990

38

L.J. Guibas, R. Sedgewick: `` A Dichromatic Framework for Balanced Trees''. Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, 8-21, 1978

39

Goldberg, R.E. Tarjan: ``A New Approach to the Maximum Flow Problem''. Journal of the ACM, Vol. 35, 921-940, 1988

40

J.E. Hopcroft, R.M. Karp: ``An O(n^2.5) Algorithm for Matching in Bipartite Graphs''. SIAM Journal of Computing, Vol. 4, 225-231, 1975

41

J.E. Hopcroft, R.E. Tarjan: ``Efficient Planarity Testing''. Journal of the ACM, Vol. 21, 549-568, 1974

42

M. Himsolt: ``GML: A portable Graph File Format''. Technical Report, Universität Passau, 1997, cf. http://www.fmi.uni-passau.de/himsolt/Graphlet/GML

43

T. Hagerup, C. Uhrig: ``Triangulating a Planar Map Without Introducing multiple Arcs'', unpublished, 1989

44

A.B. Kahn: ``Topological Sorting of Large Networks''. Communications of the ACM, Vol. 5, 558-562, 1962

45

D. Knuth and S. Levy: The CWEB System of Structured Documentation, Version 3.0. Addison-Wesley, 1993.

46

J.B. Kruskal: ``On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem''. Proc. American Math. Society 7, 48-50, 1956

47

D. Kühl, M. Nissen, K. Weihe: ``Efficient, adaptable implementations of graph algorithms''. Workshop on Algorithm Engineering, Venice, Italy, September 15-17, 1997. http://www.dsi.unive.it/wae97/proceedings/ONLY_PAPERS/pap4.ps.gz

48

D. Kühl and K. Weihe: ``Data access templates''. C++ Report, 9/7, 15 and 18-21, 1997

49

E.L. Lawler: ``Combinatorial Optimization: Networks and Matroids''. Holt, Rinehart and Winston, New York, 1976

50

S.B. Lippman: ``C++Primer''. Addison-Wesley, Publishing Company, 1989

51

G.S. Luecker: ``A Data Structure for Orthogonal Range Queries''. Proc. 19th IEEE Symposium on Foundations of Computer Science, 28-34, 1978

52

K. Mehlhorn: ``Data Structures and Algorithms''. Vol. 1-3, Springer Publishing Company, 1984

53

D.M. McCreight: ``Efficient Algorithms for Enumerating Intersecting Intervals''. Xerox Parc Report, CSL-80-09, 1980

54

D.M. McCreight: ``Priority Search Trees''. Xerox Parc Report, CSL-81-05, 1981

55

M. Mignotte: ``Mathematics for Computer Algebra''. Springer Verlag, 1992.

56

K. Mehlhorn, S. Näher: ``LEDA, a Library of Efficient Data Types and Algorithms''. TR A 04/89, FB10, Universität des Saarlandes, Saarbrücken, 1989

57

K. Mehlhorn, S. Näher: `` LEDA, a Platform for Combinatorial and Geometric Computing''. Communications of the ACM, Vol. 38, No. 1, 96-102, 1995

58

K. Mehlhorn, S. Näher: ``LEDA, a Platform for Combinatorial and Geometric Computing''. book, in preparation. For sample chapters see the LEDA www-pages.

59

K. Mehlhorn and S. Näher: ``Implementation of a sweep line algorithm for the straight line segment intersection problem''. Technical Report MPI-I-94-160, Max-Planck-Institut für Informatik, Saarbrücken, 1994.

60

K. Mehlhorn and S. Näher: ``The implementation of geometric algorithms''. In 13th World Computer Congress IFIP94, volume 1, pages 223-231. Elsevier Science B.V. North-Holland, Amsterdam, 1994.

61

M. Mignotte: Mathematics for Computer Algebra. Springer Verlag, 1992

62

K. Mulmuley: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, 1994

63

D.R. Musser and Atul Saini. STL Tutorial and Reference Guide. Addison-Wesley Publishing Company, 1995

64

S. Näher: ``LEDA2.0 User Manual''. Technischer Bericht A 17/90, Fachbereich Informatik. Universität des Saarlandes, Saarbrücken, 1990

65

M. Nissen: ``Design Pattern Data Accessor''. Proceedings of the EuroPLoP 1999.

66

M. Nissen. Graph Iterators: ``Decoupling Graph Structures from Algorithms'' (masters thesis). http://www.mpi-sb.mpg.de/marco/diplom.ps.gz

67

M. Nissen, K. Weihe: ``Combining LEDA with customizable implementations of graph algorithms''. Konstanzer Schriften in Mathematik und Informatik (no. 17), Universität Konstanz, 1996. Available at ftp://ftp.informatik.uni-konstanz.de/pub/preprints/

68

M. Nissen, K. Weihe: ``Attribute classes in Java and language extensions''. Konstanzer Schriften in Mathematik und Informatik (no. 66), Universität Konstanz, 1998. Available at ftp://ftp.informatik.uni-konstanz.de/pub/preprints/

69

M. H. Overmars: Designing the computational geometry algorithms library CGAL. In Proceedings First ACM Workshop on Applied Computational Geometry, 1996

70

F.P. Preparata, M.I. Shamos: ``Computational Geometry: An Introduction''. Springer Publishing Company, 1985

71

W. Pugh: ``Skip Lists: A Probabilistic Alternative to Balanced Trees''. Communications of the ACM, Vol. 33, No. 6, 668-676, 1990

72

N. Ramsey: ``Literate programming simplified''. IEEE Software, pages 97-105, 1994

73

M. Stoer and F. Wagner: ``A Simple Min Cut Algorithm''. Algorithms - ESA '94, LNCS 855, 141- 147, 1994

74

B. Stroustrup: ``The C++Programming Language, Second Edition''. Addison-Wesley Publishing Company, 1991

75

J.T. Stasko, J.S. Vitter: ``Pairing Heaps: Experiments and Analysis''. Communications of the ACM, Vol. 30, 234-249, 1987

76

R.E. Tarjan: ``Depth First Search an Linear Graph Algorithms''. SIAM Journal of Computing, Vol. 1, 146-160, 1972

77

R.E. Tarjan: ``Data Structures and Network Algorithms''. CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 44, 1983

78

M. Wenzel: ``Wörterbücher für ein beschränktes Universum''. Diplomarbeit, Fachbereich Informatik, Universität des Saarlandes, 1992

79

A.G. White: ``Graphs,Groups, and Surfaces''. North Holland, 1973

80

D.E. Willard: ``New Data Structures for Orthogonal Queries''. SIAM Journal of Computing, 232-253, 1985