LEA
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

TT

27. Workshop über
Komplexitätstheorie, Datenstrukturen
und Effiziente Algorithmen


Programm


09:30 Martin Löbbing, Ingo Wegener (Dortmund)
Zählen mit Binary Decision Diagrams:
Die Anzahl der Springertouren beträgt 33.439.123.484.294
09:50 Carsten Damm (Trier), Stasys Jukna (Vilnius), Jirí Sgall (Prag)
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
10:10 Sven Schuierer (Freiburg)
Optimal Robot Localization in Trees
10:30 Oliver Kullmann (Frankfurt)
Worst case-Analyse und untere Schranken für effizientere SAT-Algorithmen
10:50 Pause
11:20 Gerhard Weissenfels (Mainz)
Über die Approximierbarkeit von Färbungsproblemen für geometrische Graphklassen
11:40 Thomas Hofmeister, Hanno Lefmann (Dortmund)
A Combinatorial Design Approach to MAXCUT
12:00 Jürgen Dedorath (München), Jordan Gergov, Torben Hagerup (Saarbrücken)
More Efficient Parallel Flow Algorithms
12:20 Elias Dahlhaus (Sydney)
Ein einfacher effizienter paralleler Algorithmus für die Erkennung von Intervallgraphen
12:40 Mittagspause
13:30 Mitgliederversammlung der GI-FG 0.1.3: Parallele und verteilte Algorithmen (im Raum S2229)
14:15 Henning Fernau, Klaus-Jörn Lange, Klaus Reinhardt (Tübingen)
Ein Plädoyer für den Eigentümer
14:35 Harald Hempel (Jena)
Ein allgemeiner Optimierungsoperator
14:55 Steve Fenner (Portland), Fred Green (Worcester), Steve Homer (Boston), Alan Selman (Buffalo), Thomas Thierauf (Ulm), Heribert Vollmer (Würzburg)
On the Complements of Multivalued Functions
15:15 Pause
15:40 Hans-Jörg Burtschick (Berlin), Wolfgang Lindner (Ulm), Arfst Nickelsen (Berlin)
Über p-selektive E-bi-immune Mengen
16:00 Thomas Schwentick (Mainz)
Teilklassen von Binärem NP
16:20 Hans-Jörg Burtschick (Berlin), Heribert Vollmer (Würzburg)
Charakterisierungen von Komplexitätsklassen durch Blattsprachen und endliche Modelltheorie
16:40 Pause
17:05 Bernd Borchert (Heidelberg)
Circuit Kolmogorov Complexity
17:25 Martin Kummer (Karlsruhe)
Die Komplexität von Zufallsstrings
17:45 Werner Stein (Kaiserslautern)
Learning Environments leading to Inefficient Learnability
18:05 Ende des Workshops


Volker Heun, 1995-08-10, 1995-10-29