"Parametrisierte Algorithmen 001.ps.gz" - читать интересную книгу автора

Parametrisierte Algorithmen \Lambda

Rolf Niedermeier in Zusammenarbeit mit Jochen Alber Wilhelm-Schickard-Institut f"ur Informatik, Universit"at T"ubingen,

Sand 13, D-72076 T"ubingen [email protected]

X

k

X

k

statt

\Lambda Skript zu einer zweist"undigen Vorlesung im Sommersemester 1999 f"ur den Bereich "Theoretische Informatik" an der Universit"at T"ubingen. Das Skript ist erh"altlich "uberhttp://www-fs.informatik.uni-tuebingen.de/,niedermr/lehre/ Version vom 2. September 1999.

1

Inhaltsverzeichnis 0 Vorwort 4 1 Ein einf"uhrendes Beispiel 5 2 Standortbestimmung 8

2.1 Ans"atze zur Behandlung komplexit"atstheoretisch harter Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1 Average Case- statt Worst Case-Analyse . . . . . . . . 8 2.1.2 Approximation . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Randomisierte Algorithmen . . . . . . . . . . . . . . . 9 2.1.4 Heuristische Verfahren . . . . . . . . . . . . . . . . . . 10 2.1.5 Neue Berechnungsmodelle . . . . . . . . . . . . . . . . 10 2.1.6 Parametrisierte Algorithmen . . . . . . . . . . . . . . 10 2.2 Aspekte der Parametrisierung . . . . . . . . . . . . . . . . . . 11

2.2.1 Laufzeit-Argumente . . . . . . . . . . . . . . . . . . . 11 2.2.2 Parametrisierte Algorithmen -- eine Normalit"at? . . . 13

3 Grundlegende Definitionen 17 4 Grundlegende Methoden 21

4.1 Reduktion auf den Problemkern . . . . . . . . . . . . . . . . . 21 4.2 Tiefenbeschr"ankte Suchb"aume . . . . . . . . . . . . . . . . . . 27 4.3 Farbkodierungen und Hashing . . . . . . . . . . . . . . . . . . 33 4.4 Aufwendigere Methoden im "Uberblick . . . . . . . . . . . . . 38

4.4.1 Graphminoren . . . . . . . . . . . . . . . . . . . . . . 38 4.4.2 Beschr"ankte Baumweiten . . . . . . . . . . . . . . . . 40

5 Bez"uge zur Approximation 42

2