Analysis of Shortest Augmenting Path

Moderator: Effiziente Graphenalgorithmen

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Analysis of Shortest Augmenting Path

Beitrag von Dreamdancer »

Vielleicht kann ja nochmal schnell jemand erklärend eingreifen.

Ich verstehe nicht, wieso steht auf Folie 185 steht, dass "total time spent (...) for
relabeling the nodes is O(k1 m)" .

Ich hätte nun gedacht, jeder Knoten wird relabelt, also O(k1 n). Jeder Knoten kann maximal n mal relabelt werden, also O(n^2), was ja auch auf der nächsten Folie bestätigt wird.
Woher das m?

Grüße

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Re: Analysis of Shortest Augmenting Path

Beitrag von David »

Also so verstehe ich das:
Die Zeit pro Relabel-Operation ist abhängig von der Anzahl der inzidenten Kanten. Diese müssen nämlich jedes mal betrachtet werden. Werden einmal alle Knoten neu gelabelt, müssen also alle Kanten betrachtet werden: O(m). Wird jeder Knoten k1 mal neu gelabelt, entsprechend : O(k1 m).

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Analysis of Shortest Augmenting Path

Beitrag von Dreamdancer »

Ja, aber dieses k1 * m steht doch in der Abschätzung für admissible arcs O( k1 m + k2 ) :?:

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

Re: Analysis of Shortest Augmenting Path

Beitrag von Stille »

Hier geht es um die Gesamtzeit, die für die Suche nach zulässigen Kanten notwendig ist. Die Relabelings sind für das Auffinden von zulässigen Kanten notwendig, daher fliesst dieser Term hier auch ein.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“