Effiziente Algorithmen (bei Rump)

[Taurin]

Moin,

ich hab in meiner grandiosen Ordnung leider ein paar Seiten von meiner Mitschrift verloren. Falls hier jemand auch die Vorlesung gehört hat, wäre es nett, wenn er/sie hier ein paar Worte zu den Minimum Spanning Tree-Algorithmen von Johnsen und Tarjan schreiben könnte.

Zu Tarjan hab ich nach langer suche was im Netz gefunden:
1. Starte wie gewohnt mit dem Algortihmus von Prim
2. Breche ab, wenn der entstehnde Baum zu groß wird,
und ziehe den bisher berechneten Baum zu einem Knoten zusammen
3. Fahre bei 1. fort, benutze dazu den neuen Graphen
4. Wenn ein MST gefunden, expandiere ihn wieder

Ist das der Algorithmus, den wir in der Vorlesung hatten? Mit kommt der so unbekannt vor...

[sfix]

Hi,
ich glaube es kommt einbisschen zu spät, aber ist das Alg von Johnson eigentlich nicht eine Implementierung mit d-heaps von Prim´s alg?

[Taurin]

Ist tatsächlich ein bisschen spät: Die Prüfung hab ich schon hinter mir (und MST kam glücklicherweise nicht dran... ). Aber wenns das war, was du sagst, wäre das ja auch ganz einfach gewesen, danke.

[Dennis Worry]

Hi, hat jemand von euch beiden oder jemand der neu lesenden hier
seine Mitschrift zu effiziente Algorithmen noch ? Ich wuerde diese gerne kopieren oder einscannen - und fall sihr noch genaueres zu der Pruefungs sagen koenntet wuerde ich mich auch sehr freuen