Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Hauptseminar im WS 2004/05:
Dynamische Graphenalgorithmen

1. Single-Source-Shortest-Path-Probleme
   Literatur:
   • Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni: Fully dynamic shortest paths in digraphs with arbitrary arc weights. Journal of Algorithms, 49(1): 86-113, 2003.

2. All-Pairs-Shortest-Paths-Probleme
   Literatur:
   • Camil Demetrescu, Giuseppe F. Italiano: A new approach to dynamic all pairs shortest paths. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC'2003), S. 159-166. ACM Press, New York, 2003.

3. Verteilte All-Pairs-Shortest-Paths-Probleme
   Literatur:
   • Serafino Cicerone, Gabriele Di Stefano, Daniele Frigioni, Umberto Nanni: A fully dynamic algorithm for distributed shortest paths. Theoretical Computer Science, 297(1-3):83-102, 2003.

4. Dynamische Bäume
   Literatur:
   • Daniel Dominic Sleator, Robert Endre Tarjan: A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983.

5. Topologische Bäume
   Literatur:
   • Greg N. Frederickson: Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 14(4):781-798, 1985.

6. Topologische Bäume mit kleinem Durchmesser
   Literatur:
   • Giuseppe F. Italiano, Rajiv Ramaswami: Maintaining spanning trees of small diameter. Algorithmica, 22(3):275-304, 1998.

7. Gewurzelte Bäume
   Literatur:
   • Greg N. Frederickson: A data structure for dynamically maintaining rooted trees. Journal of Algorithms, 24(1):37-65, 1997.

8. Erreichbarkeitsbäume
   Literatur:
   • Liam Roditty, Uri Zwick: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'2004), S. 184-191. ACM Press, New York, 2004.

9. Sparsifikation
   Literatur:
   • David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig: Sparsification - a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, 1997.

10. Transformation dekrementeller in dynamische Algorithmen
    Literatur:
    • Monika R. Henzinger, Valerie King: Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing, 31(2):364-374, 2001.

11. Sampling-Techniken
    Literatur:
    • Monika R. Henzinger, Mikkel Thorup: Sampling to provide or to bound: with applications to fully dynamic graph algorithms. Random Structures and Algorithms, 11(4):369-379, 1997.

12. Transitive Hülle
    Literatur:
    • Valerie King, Garry Sagert: A fully dynamic algorithm for maintaining the transitive closure. Journal of Computer and System Sciences, 65(1):150-167, 2002.

13. Zusammenhang und minimale aufspannende Bäume
    Literatur:
    • Monika R. Henzinger, Valerie King: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502-516, 1999.

14. Minimale aufspannende Bäume in planaren Graphen
    Literatur:
    • David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffrey Westbrook, Moti Yung: Maintenance of minimum spanning forest in a dynamic plane graph. Journal of Algorithms, 13(1):33-54, 1992. Corrigendum erschien in Journal of Algorithms, 15(1):173, 1993.

15. Planaritätstests
    Literatur:
    • Zvi Galil, Giuseppe F. Italiano, Neil Sarnak: Fully dynamic planarity testing. In Proceedings 24th Annual ACM Symposium on Theory of Computing (STOC'92), S. 495-506. ACM Press, New York, 1992.

      Es gibt auch eine etwas (für das Seminar zu) lang geratene Journalversion:
      Zvi Galil, Giuseppe F. Italiano, Neil Sarnak: Fully dynamic planarity testing with applications. Journal of the ACM, 46(1):28-91, 1999.

16. Zusammenhang und minimale aufspannende Bäume in deterministischer sublinearer Zeit
    Literatur:
    • Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning trees, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723-760, 2003.