Ein Steinerbaum ist eine Menge von Strecken (oder Kanten), die eine gegebene Menge von Punkten (oder Knoten eines Graphen) miteinander verbindet. Man unterscheidet allgemeine Steinerbäume in der Ebene, solche, die nur horizontale und vertikale Strecken enthalten, und drittens Steinerbäume in Graphen. In allen drei Fällen ist das Problem, einen kürzesten Steinerbaum zu finden, NP-schwer. Im ersten Teil dieser zweistündigen Spezialvorlesung werden diese Varianten des Steinerbaumproblems näher untersucht. Wir beschreiben exakte Algorithmen (mit exponentieller Laufzeit) und polynomielle Approximationsalgorithmen. Außerdem zeigen wir die Bedeutung des Steinerbaumproblems in Anwendungen, insbesondere im VLSI-Design. Im zweiten Teil der Vorlesung betrachten wir zwei wichtige Verallgemeinerungen: Packen von Steinerbäumen und Design ausfallsicherer Netzwerke.
| Vorkenntnisse: | Grundstudium und ein wenig Graphentheorie. |
| Ort: | Gerhard-Konow-Hörsaal Lennéstr. 2 |
| Zeit: | Montags 10-12 Uhr |
ACHTUNG! | Geänderte Vorlesungszeit |
| Beginn: | 16.10.2001 |
J. Vygen