Algorithmus von Hopcroft und Tarjan

Wikimedia-Begriffsklärungsseite

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