2024-03-29T21:41:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001029082024-03-29T05:26:34Z01164:02592:07425:07658
サイクルグラフ上の経路長を短くする一方通行決定問題に対する<i>O</i>(<i>n</i> +<i> q</i> log <i>n</i>)アルゴリズムAn <i>O</i>(<i>n</i> +<i> q</i> log <i>n</i>) algorithm for the route-enabling graph orientation problem on cyclesjpnhttp://id.nii.ac.jp/1001/00102884/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=102908&item_no=1&attribute_id=1&file_no=1Copyright (c) 2014 by the Information Processing Society of Japan上智大学理工学研究科澤, 道彦n 頂点の重み付き無向グラフ G と頂点対の集合 (s1, t1),...,(sq, tq) に対し,G の orientation D で,D 内での si から ti への最短路長の,i に関する和や最大値を最小化するものを探す問題を,それぞれ min-sum,min-max 型の route-enabling graph orientation problem と呼ぶ.本文では,特に G が cycle の時に,min-sum,min-max 型共に O(n + q log n) で解くアルゴリズムを提案する.さらに,そのアルゴリズムは G が cacti の場合の時間複雑度も O(n2 + nq log q) に改善する.For a given edge weighted undirected graph G with n vertices and a set of pairs of vertices (s1, t1),...,(sq, tq), the min-sum (resp. min-max) route-enabling graph orientation problem is to find an orientation D of G which minimizes the sum (resp. max.) of the shortest distances from si to ti in D. In this paper, we propose O(n + q log n) algorithm for the problem on cycles. An O(n2 + nq log n) algorithm on cacti is introduced by our algorithm in the straight forward way.AN1009593X研究報告アルゴリズム(AL)2014-AL-1492142014-09-052014-08-28