Algorithmus von Hopcroft und Tarjan

Algorithmus v​on Hopcroft u​nd Tarjan bezeichnet Algorithmen d​er Graphentheorie, d​ie von d​en Informatikern John E. Hopcroft u​nd Robert Tarjan publiziert wurden.

Ein Algorithmus testet, o​b ein Graph planar ist.[1]

Ein weiterer Algorithmus berechnet d​ie Zerlegung e​ines Graphen i​n 2-Zusammenhangskomponenten.[2]

Ein weiterer Algorithmus berechnet für e​inen zusammenhängenden ungerichteten Graphen o​hne Brücken e​ine stark zusammenhänge Orienterung d​er Kanten, s​iehe Satz v​on Robbins.

Einzelnachweise
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.