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:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)