Graph Orientation Algorithms to minimize the Maximum Outdegree
Graph Orientation Algorithms to minimize the Maximum Outdegree
复制标题
DOI：
10.1142/s0129054107004644
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
Y. Asahiro;Eiji Miyano;H. Ono;K. Zenmyo
中科院分区：
文献类型：
--
作者：
Y. Asahiro;Eiji Miyano;H. Ono;K. Zenmyo
本文研究赋权图的边的定向问题，使得顶点的最大赋权出度最小。这个问题，例如在防护装置中的应用，通常可以被证明是[公式：见正文]-困难的。在本文中，我们首先给出了最优定向算法，在多项式时间运行以下特殊情况：（i）输入是一个未加权的图，（ii）输入图是一棵树。然后，通过使用这些算法作为子程序，我们提供了一个简单的，组合的，[公式：见正文]-近似算法的一般情况下，其中wmax和wmin分别是最大和最小的边的权重，和ε是一些小的正真实的数，取决于输入。
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 [Formula: see text]-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, [Formula: see text]-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.