Algorithmus von Hopcroft und Tarjan
aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 14. Juli 2017 um 07:04 Uhr durch imported>Wdvorak(61539).
Algorithmus von Hopcroft und Tarjan bezeichnet Algorithmen der Graphentheorie, die von den Informatikern John E. Hopcroft und Robert Tarjan publiziert wurden.
Ein Algorithmus testet, ob ein Graph planar ist.[1]
Ein weiterer Algorithmus berechnet die Zerlegung eines Graphen in 2-Zusammenhangskomponenten.[2]
Ein weiterer Algorithmus berechnet für einen zusammenhängenden ungerichteten Graphen ohne Brücken eine stark zusammenhänge Orienterung der Kanten, siehe Satz von Robbins.
Einzelnachweise
- ↑ J. Hopcroft, R. E. Tarjan: Efficient planarity testing. In: Journal of the ACM. 21, 1974, S. 549–568.
- ↑ John Hopcroft, Robert Tarjan: Algorithm 447: efficient algorithms for graph manipulation. In: Communications of the ACM. Band 16, Nr. 6, 1973, S. 372–378, doi:10.1145/362248.362272.
