Algorithmus von Hopcroft und Tarjan

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

↑ 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.

[1] J. Hopcroft, R. E. Tarjan: Efficient planarity testing. In: Journal of the ACM. 21, 1974, S. 549–568.

[2] 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.

[1]

[2]