| Graph Orientation Algorithms to (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We study the problem of orienting the edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, or more generally, a graph with identically weighted edges, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, min{ , (2-#)}-approximation algorithm for the general case, where wmax and w min are the maximum and the minimum weights of edges, respectively, and # is some small positive real number that depends on the input. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||