Ferienakademie 1999
Kurs 2: Bäume - Algorithmik und Kombinatorik

Literaturliste Algorithmik

  1. Datenstruktur: Splay-Trees (nicht vergeben)
    • D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3):652-686, 1985.
  2. Dynamic Trees und ihre Anwendung in Flußalgorithmen (Klaus Holzapfel)
    • D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences 26(3):362-391, 1983.
    • D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3):652-686, 1985.
    • A.V. Goldberg and R.E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM 35(4):921-940, 1988.
  3. Anwendung von Dynamic Trees in der algorithmischen Geometrie (nicht vergeben)
    • M.T. Goodrich and R. Tamassia. Dynamic trees and dynamic point location. SIAM Journal on Computing 28(2):612-636, 1999.
  4. Pattern-Matching in Bäumen (nicht vergeben)
    • C.M. Hoffmann and M.J. O'Donnell. Pattern matching in trees. Journal of the ACM 29(1):68-95, 1982.
    • Moshe Dubiner, Zvi Galil, and Edith Magen. Faster tree pattern matching. >Journal of the ACM 41(2):205-213, 1994.
  5. Partitionierung von Bäumen (Johannes Pfeifroth)
    • R.I. Becker and Y. Perl. The shifting algorithm technique for the partitioning of trees. Discrete Applied Mathematics 62:15-34, 1995.
  6. Kleinste gemeinsame Vorfahren (Minh Bolo Pham)
    • D. Harel and R.E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2):338-355, 1984.
    • B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing 17:1253-1262, 1988.
    • S.R. Kosaraju and A.L. Delcher. Large-scale assembly of DNA strings and space-efficient construction of suffix trees. Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing STOC'95, pp. 169-177, 1995.
  7. Datenstruktur Suffixbaum und Anwendungen (Moritz Gunnar Maaß)
    • E.M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM 23(2):262-272, 1976.
    • S.R. Kosaraju and A.L. Delcher. Large-scale assembly of DNA strings and space-efficient construction of suffix trees. Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing STOC'95, pp. 169-177, 1995.
    • S.R. Kosaraju and A.L. Delcher. Correction: Large-scale assembly of DNA strings and space-efficient construction of suffix trees. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing STOC'96, p. 659, 1996.
  8. Bäume in der Evolutionslehre I: Übereinstimmung von Bäumen (nicht vergeben)
    • M. Steel and T. Warnow. Kaikoura tree theorems: Computing the maximum agreement subtree. Information Processing Letters 48(2):77-82, 1993.
    • M. Farach and M. Thorup. Fast comparison of evolutionary trees. Information and Computation 123(1):29-37, 1995.
  9. Bäume in der Evolutionslehre II: Konstruktion Phylogenetischer Bäume (nicht vergeben)
    • S.K. Kannan and T.J. Warnow. Inferring evolutionary history from DNA sequences. SIAM Journal on Computing 23(4):713-737, 1994.
  10. Bäume in der Evolutionslehre III: Kompatibilität phylogenetischer Bäume (nicht vergeben)
    • T.J. Warnow. Tree compatibility and inferring evolutionary history. Journal of Algorithms 16(3):388-407, 1994.
  11. Edit-Distanz und Alignment von Bäumen (Carsten Isert)
    • K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing 18:1245-1262, 1989.
    • D. Shasha and K. Zhang. Fast algorithms for the unit cost editing distance between trees. Journal of Algorithms 11:581-621, 1990.
    • T. Jiang, L. Wang and K. Zhang. Alignment of trees - an alternative to tree edit. Theoretical Computer Science 143(1):137-148, 1995.
  12. Graphen mit beschränkter Baumweite (nicht vergeben)
    • H. Bodlaender. A tourist guide through treewidth. Acta Cybernetica 11, 1993.
  13. Zeichnen von Bäumen (nicht vergeben)
    • E.M. Reingold and J.S. Tilford. Tidier drawings of trees. IEEE Transactions on Software Engineering 7(2):223-228, 1981.
    • K.J. Supowit and E.M. Reingold. The complexity of drawing trees nicely. Acta Informatica 18(4):377-392, 1983.
    • J.Q. Walker II. A node-positioning algorithm for general trees. Software Practice and Experience 20(7):685-705, 1990.
    • S. Moen. Drawing dynamic trees. IEEE Software 7(4):21-28, 1990.
  14. Mediane und Broadcast-Zentren in Bäumen (nicht vergeben)
    • P.J. Slater, E.J. Cockayne, and S.T. Hedetniemi. Information dissemination in trees. SIAM Journal on Computing 10(4):692-701, 1981.
    • O. Gerstel and S. Zaks. A new characterization of tree medians with applications to distributed algorithms. Proceedings of WG'92, LNCS 657, pp. 135-144, 1993.
  15. Minimale Spannbäume (Ingo Rohloff)
    • David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM 42(2):321-328, 1995.
    • Valerie King. A simpler minimum spanning tree verification algorithm. Algorithmica 18(2):263-270, 1997.