Chapter04

Moderator: Effiziente Graphenalgorithmen

DreamFlasher
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 12. Okt 2010 12:44

Chapter04

Beitrag von DreamFlasher »

Hi,
Folie 45 in c4 bleibt mir unklar:
- Inwiefern ist C ein polinomieller Term? Für meine Begriffe ist das eine Konstante, so wie von uns beschrieben.
- Inwiefern soll "Suppose we maintain a LIST of nodes with the property that if an arc (v,w) violates the optimality condition then LIST must contain node v." begründen, dass wir nun nur noch O(m/n) haben beim Listen durchsuchen?
Viele Grüße und Danke,
Marcel
Marcel Ackermann
http://www.dreamflasher.de
Machine Learning, Natural Language Processing, Algorithms

Interesse an Machine Learning, Artificial Intelligence, Natural Language Processing? Du möchtest deine Skills und Wissen verbessern, an Wettbewerben mit anderen Begeisterten teilnehmen? Mach mit bei unserer Study Group: http://groups.google.com/group/ml-ai

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Chapter04

Beitrag von Stille »

DreamFlasher hat geschrieben:Hi,
Folie 45 in c4 bleibt mir unklar:
- Inwiefern ist C ein polinomieller Term? Für meine Begriffe ist das eine Konstante, so wie von uns beschrieben.
Genau. Ist oben auf der Folie definiert. Ist natürlich nicht notwendigerweise durch ein Polynom in Abhängigkeit von m und n beschränkt (siehe Knapsack-Aufgabe).
DreamFlasher hat geschrieben: - Inwiefern soll "Suppose we maintain a LIST of nodes with the property that if an arc (v,w) violates the optimality condition then LIST must contain node v." begründen, dass wir nun nur noch O(m/n) haben beim Listen durchsuchen?
Liste ist hier nicht gleich Liste: Zuvor haben wir alle Adjazenzlisten durchsucht (O(m)), im anderen Fall betrachten wir nur Adjazenzlisten von den Knoten in der LIST.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“