Graph Orientation Algorithms to Minimize the Maximum Outdegree

Asahiro, Y., Miyano, E., Ono, H. and Zenmyo, K.

We study the problem of orienting the edges of a weighted graph such that the maximum weighted out- degree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be NP-hard 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, minfwmax wmin ; (2�')g-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ' is some small positive real number that depends on the input.

Cite as: Asahiro, Y., Miyano, E., Ono, H. and Zenmyo, K. (2006). Graph Orientation Algorithms to Minimize the Maximum Outdegree. In Proc. Twelfth Computing: The Australasian Theory Symposium (CATS2006), Hobart, Australia. CRPIT, 51. Gudmundsson, J. and Jay, B., Eds. ACS. 11-20.

(from crpit.com) (local if available)