http://swrc.ontoware.org/ontology#TechnicalReport
Graph Orientation Problems for Multiple st-Reachability
en
Tohoku University
Sophia University
Kyushu University
Meiji University
Japan Advanced Institute of Science and Technology
Takehiro Ito
Yuichiro Miyamoto
Hirotaka Ono
Hisao Tamaki
Ryuhei Uehara
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.
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.
AN1009593X
研究報告アルゴリズム（AL）
2009-AL-125
5
1-6
2009-07-14