Algorithmus von Hopcroft und Tarjan
Zur Navigation springen
Zur Suche springen
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
[Bearbeiten | Quelltext bearbeiten]- ↑ 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.