Effiziente Kombinatorische Algorithmen

DFS:

• Was ist eine nichttrivale Eigenschaft, die wir auf ungerichteten Graphen mit Tiefensuche berechnet haben?
• Was ist eine zweifache ZHK?
• Definiere Artikulationspunkt.
• Was ist der Superstrukturgraph? Eigenschaften?
• Wie berechnen wir 2ZK genau?
• Was haben Rückkanten im Tiefensuchbaum für Eigenschaften?
• Warum funktioniert der Algorithmus?
• Wie ist die Laufzeit?

VC:

• Es wurde das Kapitel „parametrisierte Komplexität“ kurz erläutert. Wie war die Überschrift dieses Kapitels?
• Was haben wir für ein Beispiel behandelt?
• Definiere Vertex Cover.
• Wann nennen wir einen Algorithmus parametrisiert?
• Wie sah der parametrisierte Algorithmus aus der Vorlesung zu Vertex Cover aus? (Dabei wurden noch die beiden Lemmata aus der Vorlesung gefordert)
• Wie ist die Laufzeit?
• Wie können wir nun aus dem Algorithmus für das Entscheidungsproblem einen Algorithmus für das Optimierungsproblem machen?
• Was ist die Worst-Case Laufzeit dieses Algorithmus? Dafür sollte ich die beiden Laufzeitgraphen von Brute-Force und parametrisiertem Algorithmus hinzeichen. Der Schnittpunkt (Break-Even-Point), der gleichzeitig Maximum ist, ist dabei kleiner als die beiden Maxima der Algorithmen selbst.

DP:

• Wir haben das TSP betrachtet. Definieren Sie dieses.
• Wie können wir dieses Problem schneller als mit Laufzeit (n/e)^n lösen?
• Warum funktionert das?
• Wie ist die Laufzeit?