A Graph Orientation Problem
Mikhail J. Atallah · Purdue e-Pubs (Purdue University System) · 1983
We consider the following problem: Given a connected, undirected graph with a cost associated with every vertex, assign directions to its edges so that the resulting digraph is acyclic, h.as a root and is such that the sum of the costs of its sinks is as small as possible.We give a linear time algorithm for solving this problem if the costs are nonnegative.and prove that it is NP-hard if negative costs are allowed.