ダウンロード数: 168

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
IEICE_tec.rep_COMP2007-39.pdf2.38 MBAdobe PDF見る/開く
タイトル: サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム
その他のタイトル: An Optimal Online Algorithm for the Graph Exploration Problem on Cycles
著者: 森本, 尚之  KAKEN_id
宮崎, 修一  KAKEN_id  orcid https://orcid.org/0000-0003-0369-1970 (unconfirmed)
岡部, 寿男  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0003-0825-2256 (unconfirmed)
著者名の別形: Morimoto, Naoyuki
Miyazaki, Shuichi
Okabe, Yasuo
キーワード: オンラインアルゴリズム
競合比解析
グラフ探索問題
Online algorithm
Competitive analysis
Graph exploration problem
発行日: 13-Sep-2007
出版者: 電子情報通信学会
誌名: 電子情報通信学会技術研究報告
巻: 107
号: 219
開始ページ: 51
終了ページ: 57
論文番号: COMP2007-39
抄録: オンライングラフ探索問題における目的は, 探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査し, 最後に出発点に戻ることである.ある辺の存在ならびにその長さは, 探索者がその端点を訪れるまで未知である.目的達成に要した総移動距離を探索者のコストとして定める.探索対象を平面グラフとする場合, 16競合のアルゴリズムが知られている.朝廣らは, 探索対象をサイクルグラフとする場合において, 1.5競合のアルゴリズムを与えるとともに, (1.25-ε)競合のアルゴリズムは存在しないことを示した(ここでeは任意の正定数である).本稿では, サイクルグラフに対する 最適なオンラインアルゴリズムを与える.すなわち, 1+√<3>/2(≃1.366)競合のアルゴリズムを与えるとともに, (1+√<3>/2-ε)競合のアルゴリズムは存在しないことを証明する(上記と同様, εは任意の正定数である)
The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical traveling salesperson problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. It is known that there is a 16-competitive online algorithm for planer graphs. Recently, Asahiro et al. considered this problem on cycles and proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant e. In this paper, we give an optimal online algorithm for this problem; namely, we give a 1+√<3>/2(≃1.366)-competitive algorithm, and prove that there is no (1+√<3>/2-ε)-competitive algorithm for any positive constant ε.
記述: <コンピュテーション研究会(COMP)> 2007年 9月20日(木) 10:00 - 17:00, 豊橋技術科学大学 総合研究実験棟 9階セミナー室
著作権等: © 電子情報通信学会(IEICE)
URI: http://hdl.handle.net/2433/227011
関連リンク: http://www.ieice.org/ken/paper/20070920JAxI/
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。