Hopcroft and Tarjan's algorithm

from Wikipedia, the free encyclopedia

Hopcroft and Tarjan algorithm refers to graph theory algorithms published by computer scientists John E. Hopcroft and Robert Tarjan .

An algorithm tests whether a graph is planar .

Another algorithm calculates the decomposition of a graph into 2 connected components .

Another algorithm calculates a strongly connected orientation of the edges for a connected undirected graph without bridges, see Robbins' theorem .

Individual evidence

  1. ^ J. Hopcroft, RE Tarjan: Efficient planarity testing. In: Journal of the ACM. 21, 1974, pp. 549-568.
  2. ^ John Hopcroft , Robert Tarjan : Algorithm 447: efficient algorithms for graph manipulation . In: Communications of the ACM . tape 16 , no. 6 , 1973, p. 372-378 , doi : 10.1145 / 362248.362272 .