1-Baum 105

2-3-Bäume 18

A

Abschluß, transitiver 6,13

Abschwächung 103

Adjazenzlisten 4

Adleman 80

Ahuja 36,49

Ahuja, Orlin und Tarjan, Algorithmen 49

aktiv, Knoten 45

Algorithmen

von Ahuja, Orlin und Tarjan 49

von Goldberg und Tarjan 44,45

Algorithmus

All Pairs Distances 17

APD 17

beste Einfügung 108

BICON 12

für bipartite Graphen (Matching) 54,55

Branch-and-Bound 95

Branching 95

zur Derandomisierung 71

Depth-First-Search 4

deterministischer (MINCUT) 67

DFS 4

Euklidischer 82

FastCut 66

Fehlerkantenberechnung 32

generischer Preflow-Push-Algorithmus 46

Irgendein Q-S-Schnitt 68

Jacobi-Symbol-Berechnung 86

Kontraktion 64

lokal optimaler Hamiltonkreis 101

lower bound 94

zu MaxE3SAT 78

MINCUT 69

nächster Nachbar 108

optimale Einfügung 109

polynomieller Approximationsalgorithmus 96

Potenzieren 81

Rucksackproblem 93,98,99

Spannbäume und Eulerkreise 109

String Matching 31

TOP SORT 7

TSP 104

unabhängige Menge 74

UNION-FIND (schnelles FIND) 18

UNION-FIND (schnelles UNION) 19

upper bound 94

von Christofides 110

von Dijkstra 14

von Dinic 39,40

von Edmonds und Karp 37,38

von Ford und Fulkerson 33

von Goldberg und Tarjan - FIFO-Strategie 48

von Karzanov 41

von Kruskal 18

All Pair Distances 15

Algorithmus 17

All Pairs Shortest Paths 15

Alon 36

alternierend, Pfad 53

Approximationsalgorithmen,

für TSP_metr 108

polynomielle 96

Approximationsschemata, polynomielles 97

asymmetrisch 33

Automat, nichtdeterministische endliche 30

AVL-Bäume 18

B

B-Bäume 22

Back-Kanten 4

Backtracking 10

Basis, Blüten 57

Basisoperationen 46

Bäume, gewichtsbalancierte 22

bedient, Wege 45

bedingte Wahrscheinlichkeiten 70

Beispiel, zu

Adjazenzmatrix A* 15

Blüten 56

chinesischer Restsatz 88

DFS 6

Hamiltonkreisberechnung 102

Klauseln mit k Literalen 72

kleiner Wahrscheinlichkeitsraum 77

Legrendre- und Jakobisymbol 85

maximale Matchings 61

Schnittpunkte liegen in mind. zwei ZZK 9

Schnittpunkten 8

Stau und Preflow in Netzwerken 44

String-Matching 30

UNION-FIND-Datenstruktur 19

weiterer Algorithmus für bipartite Graphen 54

zahlentheoretische Grundlagen 84

Bellmore 107

besetzt, Knoten 53

beste Einfügung, Algorithmus 108

BICON, Algorithmus 12

binäre Optimierung 102

binäre Suchbäume 22

bipartit, Graphen 51

bipartite Graphen, Flußprobleme und maximale Matchings 51

Bitoperationen 13

Blatt 11

Blum 61

Blüten 56,57

Basis 57

Branch-and-Bound 93

Algorithmus 95

Branching 94

Branching-Regeln 106,107,108

Breadth-First-Search 4

Buchhaltermethode 18,19

C

Cayley 107

Carmichael-Zahl 84

Cheriyan 36

Cherkasky 36

Chiffrierfunktion 79

chinesischer Restsatz 87

Christofides, Algorithmus 110

Cross-Kanten 5

D

Datenstrukturen,

UNION-FIND 18

Vorlesung 1

Dechiffrierfunktion 79

Depth-First-Search, Algorithmus 4

Derandomisierung 70

generischer Algorithmus 71

Desaturierung 43

DFS-Nummer 4

Dictionaries 18

Diffie 80

Dinic 36,39

Algorithmus 39,40

disjunkte Zerlegung 5

Distanzen 16

Distanzmatrix 15

Durchmesser von Graphen 15

dynamische Programmierung 13,92

E

Eastman 107

Edmonds 36,37

Edmonds und Karp, Algorithmus 37,38

einfach, Netzwerk 52

Eingabegraph 8

Element, erzeugendes 83

elementare Zahlentheorie 79

endliche Schlüsselmenge 79

Erwartungswert 25

Erwartungswert (Derandomisierung) 70

erzeugendes Element 83

Euklidischer Algorithmus 82

Euler-Funktion 80

Even 61

externe Namen 18

F

F-Kanten 31

Fan-In 52

Fan-Out 52

FastCut, Algorithmus 66

Fehlerkante 31

Fehlerkantenberechnung, Algorithmus 32

Fermat, kleiner Satz von 84

FIFO-Strategie, Algorithmus von Goldberg und Tarjan 48

Flaschenhals 34

flow excess 44

Fluß 33

ganzzahlig 33

maximaler 33

Wert 33

zulässig 33

Flußalgorithmen 36

Flüsse in Netzwerken 33

Flußproblem 33,36

in bipartiten Graphen 51

Flußvergrößerung 34

Ford 33

Ford und Fulkerson, Algorithmus 33

Forward-Kanten 5

Frank 63

frei, Knoten 53

freie Kanten 53

Fulkerson 33

FV-Wege 37

FVMIN, Vorgehensweise 37

G

Gabow 36

Galil 36

Garfinkel 108

generischer Preflow-Push-Algorithmus 46

gerichtete Graphen 4

Gewicht (Derandomisierung) 70

gewichtete MINCUT Problem 67

gewichtsbalancierte Bäume 22

Gewichtsmatrix 14

Goldberg 36,44

Goldberg und Tarjan, Algorithmen 44,45

Graph, asymmetrisch 33

Graphalgorithmen, grundlegende 4

Graphen 4

bipartite 51

Durchmesser 15

gerichtet 4

Kanten 4

Knoten 4

Kreis 4

Matching 51

ungerichtete 4

Weg 4

Greedy Algorithmus 14

großer Überschuß, Knoten 49

größter gemeinsamer Teiler 81,82

Grundlagen, zahlentheoretische 83

Gruppe 90

GTI-Vorlesung 30

gültige Knotenmarkierung 45

Güte, eines Approximationsalgorithmus 71

H

Hagerup 36

Hamiltonkreis 100

lokal optimaler 101

Hamiltonsche Pfade 100

Handlungsreisender, Problem 100

Harmonische Zahlen 24

Hashing 22

Held 106

Hellman 80

Höhenbalancierung 22

I

Ibaraki 63

INDEPENDENT SET 73

Index, zahlentheoretisch 84

interne Namen 18

Inverse, multiplikative 81

Irgendein Q-S-Schnitt, Algorithmus 68

J

Jacobi-Symbol 85

Algorithmus 86

Jonker 106

K

k-Opting 102

Kante, wählbar 45

Kanten,

Back 4

Cross 5

Forward 5

freie 53

Graphen 4

satuiert 39

Tree 4

Kantenmenge 4

Kantenmengen, disjunkt 5

Kapazität 33,35

Kapazitätsfunktion 33

Kapazitätswerte 33

Karel 103

Kariv 61

Karp 36,37,106

Karzanov 36,41

Algorithmus 41

Kind 11

Kirchhoff-Regel 33

kleine Wahrscheinlichkeitsräume 76

Knoten,

aktiv 45

besetzt 53

freie 53

Graphen 4

großer Überschuß 49

Schnittpunkt 7

knotendisjunkt 60

Knotenmarkierung, gültige 45

Knuth 30

Kommunikationsnetzwerk 8

Komponente 8

Kontraktion 64

Algorithmus 64

Kostenträger 21

Kreis 4

kreisfrei 6

Kryptanalyse 80

Kryptogramm 79

Kryptogramme, Menge der 79

Kryptographie 79

kryptographische Systeme 79

kürzeste Wege 14

L

Legendre-Symbol 85

Lengauer, Thomas 63

lexikographische Sortierung 22

Liste der Arbeiten zum Flußproblem 36

Little 103

lokale Suche 101

low point 10

Low-Wege 11

Lower Bound 94

M

M-Kanten 53

Maheshvari 36

Malhotra 36

Malone 107

Markierungsalgorithmus, Flüsse 33

Matching,

in ungerichteten Graphen 51

maximales 51

Matrizenmultiplikation 13

Matrizenmultiplikation, Schulmethode für 13

Matrizenprodukt, boolesches 13

MAXCUT, Problem 63

MaxE3SAT 71,72

deterministischer Algorithmus 78

MaxEkSAT 71

MAXFLOW 35

maximal, Fluß 33

maximale Matchings 51

graphentheoretische Charakterisierung 53

in bipartiten Graphen 51

Maximierungsprobleme, Branch-and-Bound 93

Mehlhorn 36

Menge,

der Kryptogramme 79

unabhängig (Derandomisierung) 73

Metaknoten 64

Methode, ungarische 107

Micali 61

MINCUT 35

Algorithmus 69

Problem 63

minimale Spannbäume 18,103

Morris 30

Multigraph 64

multiplikative Inverse 81

Murty 103,107

Muster 30

Mustererkennung 30

N

Naamad 36

Nachbarn 9

Nachricht 79

Nachrichtenmenge 79

nächster Nachbar, Algorithmus 108

Nagamochi 63

Namen,

externe 18

interne 18

natürliche binäre Suchbäume 23

Nerode-Relation 30

Netzwerk 8,33

einfach 52

nichtdeterministische endliche Automat 30

Niveaunetzwerk 39

O

optimale Einfügung, Algorithmus 109

Optimierung, binäre 102

Ordnung,

einer Zahl 83

partielle 6

totale 22

Orlin 36,49

P

Paritäten 16

partielle Ordnung 6

Path Compression 20

Pattern 30

Pfad,

alternierend 53

verbessernd 53

Pfade, Hamiltonsche 100

Phasennummer 50

polynomielle Approximationsalgorithmen 96

polynomielles Approximationsschemata 97

Potentialfunktion 31

Potenzen 81

Potenzieren, Algorithmus 81

Präfix 30

Pramodh Kumar 36

Pratt 30

Preflow 44

Preflow-Push Algorithmen 44

Primzahl 80,83

Primzahlpotenz 76

Primzahltest, probabilistischer von Solovay und Strassen 88

Prioritätenvergabe 29

Priority Queue 14

Priority-Queue-Eigenschaft 23

probabilistischer Primzahlentest von Solovay und Strassen 88

Problem

des Handlungsreisenden 51,100

gewichtetes MINCUT 67

MAXCUT 63

MINCUT 63

Programmierung, dynamische 13,92

pseudopolynomiell 35

public-key-cryptosystems 80

Q

quadratfrei 84

quadratischer Rest 83

quadratisches Reziprozitätsgesetz 86

Quelle 33

Query Zeit 32

R

Randomisierungsansatz, Treaps 23

Rang 20

Ranggruppen 21

Reduktion, des Wahrscheinlichkeitsraumes 75

regulär, Sprache 30

Relation 6

Relaxation 103

Rest, quadratischer 83

Restgraph 8

Flüsse 44

Restkapazität 41

Restsatz, chinesischer 87

Reziprozitätsgesetz, quadratisches 86

Rivest 80

Rot-Schwarz-Bäume 22

Rotationen 24

RSA-System 79

Rucksackproblem 92

Algorithmus 93,98,99

eingeschränktes 93

S

satuiert 39

Satz von Fermat (kleiner) 84

Schlüssel (kryptographisch) 79

öffentlich 80

Schlüsselmenge,

dynamische 22

endliche 79

Schnittpunkt, Knoten 7

Schulmethode, ggT 82

secret-key-cryptosystems 80

Senke 33

Shamir 80

Shapiro 107

Shiloach 36

Simulated Annealing 102

Sleator 36

Smith 106,107

Solovay 88

Spannbäume,

minimale 18,103

und Eulerkreise, Algorithmus 109

spannender Wald 4

Sperrfluß 39

Sprache, reguläre 30

Srinivasan 107

Stack 12

starke Zusammenhangskomponenten 7

Stau 41,44

Stoer 63

Strafen 105

diskontierte 105

Strassen 88

Strassens Multiplikationsalgorithmus 15

String 30

String Matching 30

Algorithmus 31

Suchbaum-Eigenschaft 23

Suchbäume,

binäre 22

natürliche binäre 23

Suche, lokale 101

Suffix 30

guter 30

Sweeney 103

Symbol,

Jacobi 85

Legendre 85

Systeme, kryptographisches 79

T

T-Baum 5

T-Wald 5

T-Weg 5

Tarjan 36,44,49

Teilbaum 5

Teiler, größter gemeinsamer 81,82

Teilstring 30

Thompson 106,107

TOP SORT, Algorithmus 7

topologisches Sortieren 4

transitiver Abschluß 6,13

Traveling Salesman Problem 100

Treaps 22

Aufspaltung 28

einfügen 27

löschen 27

Prioritätenvergabe 29

Rotationen 27

Suche 24

Vereinigung 28

Tree-Kanten 4

TSP 100

Algorithmus 104

TSPE 100

TSP_Euklid 100

TSP_metr 100

Approximationsalgorithmen 108

TSP_sym 100

U

Überschuß 44

unabhängig,

Menge (Derandomisierung) 73

Zufallsvariablen 75

unabhängige Menge, deterministischer Algorithmus 74

ungarische Methode 107

ungerichtete Graphen 4

UNION-FIND 18

Algorithmus (schnelles FIND) 18

Algorithmus (schnelles UNION) 19

UNION-FIND-Datenstrukturen 18

Universum 22

Unterbaum 12

Untergruppe 90

Upper Bound 93

V

Vazirani 61

verbessernd, Pfad 53

Vertex Cover Problem 51

Vishkin 36

VLSI-Design 63

Vogelnant 106

W

Wagner 63

wählbar, Kante 45

Wahrscheinlichkeit 26

Wahrscheinlichkeit (Derandomisierung) 70

Wahrscheinlichkeiten, bedingte 70

Wahrscheinlichkeitsraum, Definition 76

Wahrscheinlichkeitsräume, kleine 76

Wahrscheinlichkeitsraum, Reduktion 75

Wald, spannender 4

Wälder, kreisfrei 6

Weg, Graphen 4

Wege,

bedient 45

kürzeste 14

Wert, Fluß 33

Wörterbücher 18

Wurzel 11

Z

Zahl, Carmichael 84

zahlentheoretische Grundlagen 83

Zahlentheorie, elementare 79

Zerlegung, disjunkte 5

Zn 83

Zufallsbits 70

Zufallsvariable 25

Zufallsvariable (Derandomisierung) 70

Zufallsvariablen, k-fach unabhängig 75

Zufallszahlen (Derandomisierung) 70

zulässig, Fluß 33

Zuordnungsproblem 107

zusammenhängend, zweifach 7

Zusammenhangskomponenten, starke 4,7

zweifach zusammenhängend 7

Zweizusammenhangskomponenten 4,7