2022-05-16T15:26:03Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000624582020-04-01T00:33:29Z01164:02592:05623:05683
Graph Orientation Problems for Multiple st-ReachabilityGraph Orientation Problems for Multiple st-Reachabilityenghttp://id.nii.ac.jp/1001/00062458/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=62458&item_no=1&attribute_id=1&file_no=1Copyright (c) 2009 by the Information Processing Society of JapanTohoku UniversitySophia UniversityKyushu UniversityMeiji UniversityJapan Advanced Institute of Science and TechnologyTakehiro, ItoYuichiro, MiyamotoHirotaka, OnoHisao, TamakiRyuhei, UeharaConsider 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-1255162009-07-142009-08-19