Given an undirected graph, one can assign directions to each of the edges of the graph, thus orienting the graph. To be as egalitarian as possible, one may wish to find an orientation such that no vertex is unfairly hit with too many arcs directed into it. We discuss how this objective arises in problems resulting from telecommunications. We give optimal, polynomial-time algorithms for: finding an orientation that minimizes the lexicographic order of the indegrees and finding a strongly-connected orientation that minimizes the maximum indegree. We show that minimizing the lexicographic order of the indegrees is NP-hard when the resulting orientation is required to be acyclic.
consider the edge-weighted version of the unconstrained problem @cite_16 . They build on the work of Venkateswaran and give a combinatorial @math -approximation algorithm where @math and @math are the maximum and minimum weights of edges respectively, and @math is a constant which depends on the input @cite_16 . Klostermeyer considers the problem of reorienting edges (rather than whole paths) so as to create graphs with given properties, such as strongly connected graphs and acyclic graphs @cite_7 . De Fraysseix and de Mendez show that they can find an indegree assignment of the vertices given a particular properties @cite_3 . In our work we are searching for a particular degree assignment not known a priori.
@cite_16 @cite_3 @cite_7
2033433572 1562280270 64043337
This paper studies the problem of orienting all 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 -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, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, -approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and e is some small positive real number that depends on the input. Regular orientations, that is orientations such that almost all the vertices have the same indegree, relates many combinatorial and topological properties, such as arboricity, page number, and planarity. These orientations are a basic tool in solving combinatorial problems that preserve topological properties. Planar augmentations are a simple example of such problems.