TY - GEN

T1 - Graph Orientation Algorithms to Minimize the Maximum Outdegree

AU - Asahiro, Yuichi

AU - Miyano, Eiji

AU - Ono, Hirotaka

AU - Zenmyo, Kouhei

PY - 2006

Y1 - 2006

N2 - 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 ex-ample, 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 sim-ple, combinatorial, min{wmax/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.

AB - 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 ex-ample, 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 sim-ple, combinatorial, min{wmax/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.

UR - http://www.scopus.com/inward/record.url?scp=84863571152&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863571152&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84863571152

SN - 1920682333

SN - 9781920682330

T3 - Conferences in Research and Practice in Information Technology Series

BT - Theory of Computing 2006 - Proceedings of the 12th Computing

T2 - Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006

Y2 - 16 January 2006 through 19 January 2006

ER -