Trees - the ubiquitous structure in computer science and
mathematics
St.
Petersburg, 9.3 - 19.3. 2008
Within the scope of the "Joint Advanced Student School
- JASS'2008" in St. Petersburg (March 9 - March 19), we offer the course "Trees - the ubiquitous structure in computer science and
mathematics".
Directors:
Prof. Dr. Yu. V. Matiyasevich (Steklov
Institute, St. Petersburg)
Prof. Dr. E. W.
Mayr (TU München)
Assistant:
D. Chibisov
D. Karpov
Application:
The course addresses highly motivated and interested students. Active preparation
and contribution of the participants will be required. The course language
is English. Expenses for travel, board and lodging of german participants
are covered by the school.
Application deadline for GERMAN applicants: January
25, 2008.
Application form: PDF
.
German applicants should send their applications
to D. Chibisov.
Russian
applicants should send their applications to Prof.
Dr. Yu. V. Matiyasevich.
Organization:
Every participant is expected to give a talk and
to prepare a paper on the topic of his/her talk. Some help is provided on
the organizational stuff page
Course Description:
Trees as both data
structure and a class of graphs play an important role in mathematics,
computer science, and engineering.
Especially algorithmic questions about trees, is an important
issue for various applications. The course is devoted, besides the
fundamentals of graph theory and algorithmics,
to applications of trees in mathematics and computer
science.
Tobias Lieber
Introduction to graph teory, balanced trees (AVL, 2-3), splay trees
Literature: [1], [2], [3]
|
|
Gravin Nikolai
Spanning trees with large numbers of leaves
Literature: ...
|
|
Maximilian Schlund
Minimum spanning trees
Literature: [4], [5], [6]
|
|
Khristoforov Mikhail
Tutte Polynomial
Literature: ...
|
|
Caroline Löbhard
Suffix trees
Literature: [7], [8], [9], [10], [11], [12]
|
|
Shmakov Kirill
Tree reconstruction
Literature: [24], [25]
|
|
Fayssal El Moufatich
Lowest common ancestors
Literature: [16], [17], [18], [19] , [20], [21]
|
|
Smal Alexander
Tree isomorphism
Literature [26]
|
|
Smirnova Elena
Pattern matching in trees
Literature: .
|
|
Stephan Holzer
Bounded tree width
Literature: [21], [22], ...
|
|
Yaroslavtsev Grigory
Plane trees and Chebyshev polynomials
Literature: [27], [28], [29], [30]
|
|
Konstantin Pieper
The number of spanning trees in a graph
Literature: [23], ...
|
|
Literature (will be completed...):
[1] T. Ottmann and P. Widmayer: Algorithmen und
Datenstrukturen. Bibliographisches Institut:
Mannheim-Wien-Zürich, 1990
[2] K. Mehlhorn: Data structures and algorithms 1: Sorting and
searching. EATCS Monographs on Theoretical Computer Science.
Springer-Verlag, Berlin, 1984.
[3] D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3):652-686, 1985.
[4] D. R. Karger, P. N. Klein, and R. E. Tarjan: A randomized
linear-time algorithm to find minimum spanning trees. Journal of the
ACM 42(2):321-328, 1995.
[5] V. King: A simpler minimum spanning tree verification algorithm.Algorithmica 18(2):263-270, 1997.
[6] S. Pettie and V. Ramachandran: An optimal minimum spanning tree
algorithm. http://www.cs.utexas.edu/users/vlr/papers/optmsf.pdf
[7] M. Farach-Colton. Optimal Suffix Tree Construction with Large Alphabets. ftp://ftp.cs.rutgers.edu/pub/farach/Suffix.ps.Z
[8] E.M. McCreight: A space-economical suffix tree construction algorithm. Journal of the ACM 23(2):262-272, 1976.
[9] 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.
[10] 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.
[11] D. Gusfield: Algorithms on strings, trees, and sequences: Computer
science and computational biology.Cambridge University Press:
Cambridge, 1997
[12] E. Ukkonen: On-line construction of suffix trees. Algorithmica, vol 14, pp. 249-260, 1995.
[13] C.M. Hoffmann and M.J. O'Donnell: Pattern matching in trees. Journal of the ACM 29(1):68-95, 1982.
[14] Moshe Dubiner and Zvi Galil and Edith Magen: Faster tree pattern matching. Journal of the ACM 41(2):205-213, 1994
[15] Richard Cole and Ramesh Hariharan and Piotr Indyk: Fast Algorithms
for Subset Matching and Tree Pattern Matching.
http://drona.csa.iisc.ernet.in/~ramesh/sfiles/26.ps.gz
[16] D. Harel and R.E. Tarjan. Fast algorithms for finding nearest
common ancestors. SIAM Journal on Computing 13(2):338-355, 1984.
[17] B. Schieber and U. Vishkin. On finding lowest common ancestors:
Simplification and parallelization. SIAM Journal on Computing
17:1253-1262, 1988.
[18] 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.
[19] M.A. Bender and M. Farach-Colton: The LCA problem revisited. http://www.cs.sunysb.edu/~bender/pub/lca.ps
[20] S. Alstrup and C. Gavoille and H. Kaplan and T. Rauhe: Nearest
common ancestors: A survey and a new distributed algorithm
http://www.it-c.dk/research/algorithms/Kurser/AD/2002E/Uge6/nca.pdf
[21] H. Bodlaender: A tourist guide through treewidth. Acta Cybernetica 11, 19
[22] A. Andrzejak: An algorithm for the Tutte polynomials of graphs of
bounded treewidth. Discrete Mathematics August 1998, Volume 190 Issue
1-3
[23] E. W. Mayr, A. Z. Broder: Counting minimum weight spanning trees.
[24] Kelly, Paul J.: A congruence theorem for trees. (English) Pac. J. Math. 7, 961-968 (1957).,
[25] Bondy, J.A.; Hemminger, R.L.:Graph reconstruction - a survey. (English) J. Graph Theory 1, 227-268 (1977)
[26] Campbell, Douglas M.; Radford, David: Tree isomorphism algorithms:
Speed vs. clarity. (English) [J] Math. Mag. 64, No.4, 252-261 (1991).
[27] Shabat, George; Zvonkin, Alexander: "Plane trees and algebraic numbers",
in Barcelo, Helene (ed.) et al., Proc. Jerusalem combinatorics '93; www.labri.fr/perso/zvonkin/Research/shabzvon.ps.gz
[28] Yu.Matiyasevich "Generalized Chebyshev polynomials"; http://logic.pdmi.ras.ru/~yumat/Journal/jcontord.htm
[29] Yu.Matiyasevich "How to draw a tree correctly"; http://www.pims.math.ca/science/2000/distchair/matiyasevich/colloq.html
[30] Pastor, A.V "Generalized Chebyshev polynomials and Pell-Abel equation",
Fundam. Prikl. Mat. 7, No.4, 1123-1145, 2001: http://www.emis.de/journals/FPM/eng/k01/k014/k01410h.htm