Graph Orientation Problems for Multiple st-Reachability

概要

論文の詳細を見る
Consider the situation in which we wish to give one-way restrictions to aisles in a limited area, such as an industrial factory. We model this situation as graph orientation problems, where multiple st-pairs are given together with an edge-weighted graph and we seek an orientation that minimizes some objective function reflecting directed st-distances under the orientation. In this paper, we introduce two objectives, and study the corresponding two minimization problems: the first is min-sum type, and the second is min-max type. We first show that both min-sum orientation and min-max orientation problems are strongly NP-hard for planar graphs, and that min-max orientation remains NP-hard even for cacti. We then show that both problems can be solved in polynomial-time for cycles. Finally, we consider the problems restricted to cacti. Then, min-sum orientation can be solved in polynomial-time, and minmax orientation admits a polynomial-time 2-approximation algorithm and a pseudo-polynomial-time algorithm.
一般社団法人情報処理学会の論文
2009-07-14