Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Seminar: Schnelle Algorithmen für baumartige Graphen

Zeit : Do 14:15 - 16:00, Raum S2229

[Zusammenfassung] [Themenliste] [Termine]

Zusammenfassung

Die folgenden Themen stehen zur Auswahl:

1. Lösung NP-harter Probleme in linearer Zeit
   [1] S. Arnborg, A. Proskurowski: Linear Time Algorithms for NP-hard Problems Restricted to Partial k-Trees. Discrete Applied Mathematics 23 (1989) 11--24.
2. Erkennung partieller k-Bäume
   [2] S. Arnborg, D.G. Corneil, A. Proskurowski: Complexity of Finding Embeddings in a k-Tree. SIAM Journal on Algebraic Discrete Methods 8(2) (1987) 277--284.
3. Partitionierungsprobleme in partiellen k-Bäumen
   [3] A. Gupta, D. Kaller, S. Mahajan, T. Shermer: Vertex Partitioning Problems On Partial k-Trees. Proceedings of the 5th Scandinavian Workshop on Algorithm Theory SWAT'96, LNCS 1097, 161--172.
4. Graphen mit beschränkter Baumweite und partielle k-Bäume
   [4] H. Bodlaender: Classes of Graphs with Bounded Treewidth. Technical Report RUU-CS-86-22, Dept. of Computer Science, Utrecht University.
5. Anwendung beschränkter Baumweite auf disjunkte Pfad-Probleme
   [5] P. Scheffler: A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-Width. Technischer Bericht 396/1994, Fachbereich 3, Mathematik, TU Berlin.
6. Anwendung beschränkter Baumweite auf ein Scheduling-Problem
   [6] D. Kaller, A. Gupta, T. Shermer: The X_t-Coloring Problem. Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science STACS'95, LNCS 900, 409--420.
7. Isomorphie-Erkennung in partiellen k-Bäumen
   [7] H. Bodlaender: Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees. Journal of Algorithms 11 (1990) 631--643.
8. Triangulierung mit Anwendungen für phylogenetische Bäume
   [8] H. Bodlaender, T. Kloks: A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs. Journal of Algorithms 15 (1993) 160--172.
9. Dynamisches Programmieren für Dominierungsprobleme in k-Bäumen
   [9] D.G. Corneil, J.M. Keil: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees. SIAM Journal on Algebraic Discrete Methods 8(4) (1987) 535--543.
10. Dominierungsprobleme in partiellen k-Bäumen
    [10] J.A. Telle, A. Proskurowski: Practical Algorithms on Partial k-Trees with an Application to Domination-Like Problems. Proceedings of the Third Workshop on Algorithms and Data Structures WADS'93, LNCS 709.
11. Leicht lösbare Probleme für partielle k-Bäume
    [11] S. Arnborg, J. Lagergren, D. Seese: Easy Problems for Tree-Decomposable Graphs. Journal of Algorithms 12 (1991) 308--340.
12. Grundlagen zum Konzept der Baumweite
    [12] N. Robertson, P.D. Seymour: Graph Minors. II. Algorithmic Aspects of Tree-Width. Journal of Algorithms 7 (1986) 309--322.
13. Effiziente Erkennung von Graphen mit Baumweite <= 4
    [13] D.P. Sanders: On Linear Recognition of Tree-Width at Most Four. SIAM Journal of Discrete Mathematics 9(1) (1995) 101--117.

Die Themenliste mit Literaturangaben als PostScript-Datei.

Termine

Weitere Auskünfte erteilt Thomas Erlebach.