Algorithmus von Hopcroft und Tarjan

aus Wikipedia, der freien Enzyklopädie
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]
  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.