-
Convex Hulls
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapters 1 and 11.
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapters 1 and 11.
-
Line Segment Intersection
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapter 2.
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapter 2.
-
Voronoi Diagrams
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapter 7.
- M. de Berg, O. Cheong, M.J. van Kreveld, M.H. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer 2008. ISBN 9783540779735. https://doi.org/10.1007/978-3-540-77974-2. Chapter 7.
-
Fibonacci Heaps
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. https://dl.acm.org/doi/book/10.5555/1614191. Chapter 19.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. https://dl.acm.org/doi/book/10.5555/1614191. Chapter 19.
-
Min-Cut
- M. Stoer, F. Wagner. A simple min-cut algorithm. Journal of the ACM. 44(4):585, 1997. doi:10.1145/263867.263872
- D.R. Karger, C. Stein. A New approach to the minimum cut problem. J. ACM 43(4): 601-640, 1996. doi:10.1145/234533.234534
Material also in R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995, pages 7-9 and 289-295.
- M. Stoer, F. Wagner. A simple min-cut algorithm. Journal of the ACM. 44(4):585, 1997. doi:10.1145/263867.263872
-
Paging and Caching
- D.D. Sleator, R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. doi:10.1145/2786.2793
- A. Fiat, R.M. Karp, M. Luby, L.A. McGeoch, D.D. Sleator, N.E. Young. Competitive paging algorithms. J. Algorithms, 12(4): 685-699, 1991. doi:10.1016/0196-6774(91)90041-V
- D.D. Sleator, R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. doi:10.1145/2786.2793
-
Approximation Algorithms: Basic Results
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. https://dl.acm.org/doi/book/10.5555/1614191. Chapter 35.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. https://dl.acm.org/doi/book/10.5555/1614191. Chapter 35.
-
Online Matching
- R.M. Karp, U.V. Vazirani, V.V. Vazirani. An optimal algorithm for on-line bipartite matching. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 352-358, 1990. < doi:10.1145/100216.100262
- B. Birnbaum, C. Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80-87, 2008. doi:10.1145/1360443.1360462
- R.M. Karp, U.V. Vazirani, V.V. Vazirani. An optimal algorithm for on-line bipartite matching. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 352-358, 1990. < doi:10.1145/100216.100262
-
Selforganizing Data Structures
- D.D. Sleator, R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2): 202-208, 1985.
doi:10.1145/2786.2793
- N. Reingold, J. Westbrook, D.D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica 11(1):15-32, 1994.
doi:10.1007/BF01294261
- D.D. Sleator, R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2): 202-208, 1985.
doi:10.1145/2786.2793
-
Approximation Algorithms: Greedy and Local Search
- D.P. Williamson, D.B. Shmoys. The Design of Approximation Algorithms.. Cambridge University Press 2011. ISBN ISBN 978-0-521-19527-0. https://www.designofapproxalgs.com/. Chapter 2.
- D.P. Williamson, D.B. Shmoys. The Design of Approximation Algorithms.. Cambridge University Press 2011. ISBN ISBN 978-0-521-19527-0. https://www.designofapproxalgs.com/. Chapter 2.
Weitere Themen (kein Vortrag)