Category Archives: Dynamic Algorithms

Topics of the next few lectures

The lectures were based on the following papers:
8. Lecture by Erik Demaine on Van Emde Boas trees: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf
9. Lecture by Erik Demaine on Ordered List Maintenance: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L14/lecture14.pdf
11. Paper on pattern matching in dynamic texts: http://www.cs.au.dk/~gerth/papers/diku-98-27.pdf

Topics for the first few lectures

The lectures were based on the following papers:
1. A data structure for dynamic trees by Sleator and Tarjan 1982,  https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
2. Lecture on dynamic graph connectivity by Virginia V. Williams http://theory.stanford.edu/~virgi/cs267/lecture10.pdf
3. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications by Frederickson 1984, https://csclub.uwaterloo.ca/~gzsong/papers/Data%20Structures%20for%20On-Line%20Updating%20of%20Minimum%20Spanning%20Trees,%20with%20Applications.pdf
4. Dynamic Transtive Closure via Dynamic Matrix Inverse by Sankowski 2004, www.mimuw.edu.pl/~sank/pub/sankowski_focs04.ps
5. Subquadratic Algorithm for Dynamic Shortest Distances by Sankowski 2005, http:///chapter/10.1007%2F11533719_47
6. A New Approach to Dynamic All Pairs Shortest Paths by Demetrescu and Italiano 2003, www.dis.uniroma1.it/~demetres/docs/dapsp-full.pdf
7. Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles by Thorup 2004, http://link.springer.com/chapter/10.1007%2F978-3-540-27810-8_33