A strong orientation of a given bridgeless undirected graph may be found in [[linear time]] by performing a [[depth-first search]] of the graph, orienting all edges in the depth-first search tree away from the tree root, and orienting all the remaining edges (which must necessarily connect an ancestor and a descendant in the depth-first search tree) from the descendant to the ancestor.<ref>{{harvtxt|Vishkin|1985}} credits this observation to {{harvtxt|Atallah|1984}}, and {{harvtxt|Balakrishnan|1996}} credits it to {{harvtxt|Roberts|1978}}. But as {{harvtxt|Clark|Holton|1991}} point out, the same algorithm is already included (with the assumption of [[k-vertex-connected graph|2-vertex-connectivity]] rather than 2-edge-connectivity) in the seminal earlier work of {{harvtxt|Hopcroft|Tarjan|1973}} on depth-first search.</ref> Although this algorithm is not suitable for [[parallel computer]]s, due to the difficulty of performing depth-first search on them, alternative algorithms are available that solve the problem efficiently in the parallel model.<ref>{{harvtxt|Vishkin|1985}}.</ref> Parallel algorithms are also known for finding strongly connected orientations of mixed graphs.<ref>{{harvtxt|Soroker|1988}}.</ref>
==Applications==
Line 105:
| title = Algorithm 447: efficient algorithms for graph manipulation
