Algorithms and Complexity
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. If an undirected graph G with bridges is given, together with a list of ordered pairs of vertices that must be connected by directed paths, it is possible in polynomial time to find an orientation of G that connects all the given pairs, if such an orientation exists. However, the same problem is NP-complete when the input may be a mixed graph.
It is #P-complete to count the number of strong orientations of a given graph G, even when G is planar and bipartite. However, for dense graphs (more specifically, graphs in which each vertex has a linear number of neighbors), the number of strong orientations may be estimated by a fully polynomial-time randomized approximation scheme. The problem of counting strong orientations may also be solved exactly, in polynomial time, for graphs of bounded treewidth.
Read more about this topic: Strong Orientation
Famous quotes containing the word complexity:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)