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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)