next up previous contents index
Next: Index Up: Version 6.6 The LEDA Previous: Code examples for the   Contents   Index

Bibliography

1
H. Alt, N. Blum, K. Mehlhorn, M. Paul: ``Computing a maximum cardinality matching in a bipartite graph in time O(n1.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
B. Balkenhol, Yu.M. Shtarkov: ``One attempt of a compression algorithm using the BWT''. Preprint 99-133, SFB343, Fac. of Mathematics, University of Bielefeld, 1999

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

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

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

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

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

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

14
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.

15
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.

16
C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra: ``A strong and easily computable separation bound for arithmetic expressions involving radicals´´. Algorithmica, Vol.27, 87-99, 2000.

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

18
M. Burrows, D.J. Wheeler. ``A Block-sorting Lossless Data Compression Algorithm''. Digital Systems Research Center Research Report 124, 1994.

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

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

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

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

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

24
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

25
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

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

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

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

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

30
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.

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

32
P. Fenwick: ``Block Sorting Text Compression - Final Report''. Tech. Rep. 130, Dep. of Comp. Science, University of Auckland, 1996

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

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

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

36
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

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

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

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

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

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

42
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

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

44
J.E. Hopcroft, R.M. Karp: ``An O(n2.5) Algorithm for Matching in Bipartite Graphs''. SIAM Journal of Computing, Vol. 4, 225-231, 1973

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

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

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

48
D.A. Huffman: ``A Method for the Construction of Minimum Redundancy Codes''. Proc. IRE 40, 1098-1101, 1952

49
T. Iwata, K. Kurosawa: ``OMAC: One-Key CBC MAC''. Proc. Fast Software Encryption (FSE), LNCS 2887, 129-153, 2003

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

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

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

53
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

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

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

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

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

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

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

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

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

62
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

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

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

65
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.

66
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.

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

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

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

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

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

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

73
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/

74
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/

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

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

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

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

79
S. Schmitt: ``Improved separation bounds for the diamond operator''. Technical Report ECG-TR-36-31-08-01, 2004

80
B. Schneier: ``Applied Cryptography, Second Edition''. John Wiley and Sons, 1996

81
D. Shkarin: ``PPM: one step to praticality''. Proc. IEEE Data Compression Conf. (DCC'2002), 202-211, 2002

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

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

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

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

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

87
J.S. Vitter: ``Dynamic Huffman Coding''. ACM Transactions on Mathematical Software, Vol. 15, No. 2, 158-167, 1989

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

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

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

91
J.W.J. Williams: ``Algorithm 232 (heapsort)´´. Communications of the ACM, Vol. 7, 347-348, 1964

92
I.H. Witten, M. Radford and J.G. Cleary: ``Arithmetic Coding for Data Compression''. Communications of the ACM, Vol. 30, 520-540, 1987

93
J. Ziv and A. Lempel: ``A universal algorithm for sequential data compression''. IEEE Transactions on Information Theory, Vol. 30(3), 337-343, 1977

94
J. Ziv and A. Lempel: ``Compression of individual sequences via variable-rate coding'' IEEE Transactions on Information Theory, Vol. 24(5), 530-536, 1978

95
S. Näher, O. Zlotowski: ``Design and Implementation of Data Types for Static Graphs''. ESA, 2002