Diskussion:Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes

Ist hier nach Minty (dort Seite 8) nicht stets genau eine Regel anwendbar und der Algorithmus deterministisch?--goiken 00:26, 5. Dez. 2009 (CET)

Ich bezog mich in der Darstellung (ohne das zu schreiben; mein Fehler) auf ungerichtete Graphen. Man müsste den Artikel sowieso mal verbessern, ich habe leider in den nächsten Tagen wahrscheinlich keine Zeit dafür. Über den gerichteten Fall müsste ich nochmal nachdenken. -- Glotzfrosch 10:28, 9. Dez. 2009 (CET)

Minty behauptet ja nur Eindeutigkeit für EINE Kante - Tarjans "Algorithmus" lässt gerade offen, welche Kante zur Entscheidung gewählt wird. Graf Alge (Diskussion) 16:55, 15. Nov. 2014 (CET)

Wo veröffentlicht

Das ist doch wohl nicht der einzige Algorithmus von Tarjan über minimale Spannbäume (der englische Artikel zitiert Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery, 42 (2): 321–328, der Algorithmus ist aber randomisiert, davon ist hier nicht die Rede). Der Text hier klingt eher danach, dass er etwas über Greedy Algorithmen bewiesen hat oder (in seinem Lehrbuch ?) eine einheitliche Behandlung gegeben hat. Die grundlegenden Greedy-Algorithmen hierzu stammen ja nicht von ihm sondern sind älter.--Claude J (Diskussion) 20:41, 19. Mai 2022 (CEST)

Aus einer Mitschrift der Algorithmen-Vorlesung von Wagner habe ich entnommen,dass da von Färbemethode von Tarjan die Rede ist, entsprechend angepasst.--Claude J (Diskussion) 16:28, 20. Mai 2022 (CEST)