Access count of this item: 114

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2007-39.pdf2.38 MBAdobe PDFView/Open
Title: サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム
Other Titles: An Optimal Online Algorithm for the Graph Exploration Problem on Cycles
Authors: 森本, 尚之  kyouindb  KAKEN_id
宮崎, 修一  kyouindb  KAKEN_id
岡部, 寿男  kyouindb  KAKEN_id
Author's alias: Morimoto, Naoyuki
Miyazaki, Shuichi
Okabe, Yasuo
Keywords: オンラインアルゴリズム
競合比解析
グラフ探索問題
Online algorithm
Competitive analysis
Graph exploration problem
Issue Date: 13-Sep-2007
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
Volume: 107
Issue: 219
Start page: 51
End page: 57
Thesis number: COMP2007-39
Abstract: オンライングラフ探索問題における目的は, 探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査し, 最後に出発点に戻ることである.ある辺の存在ならびにその長さは, 探索者がその端点を訪れるまで未知である.目的達成に要した総移動距離を探索者のコストとして定める.探索対象を平面グラフとする場合, 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 ε.
Description: <コンピュテーション研究会(COMP)> 2007年 9月20日(木) 10:00 - 17:00, 豊橋技術科学大学 総合研究実験棟 9階セミナー室
Rights: © 電子情報通信学会(IEICE)
URI: http://hdl.handle.net/2433/227011
Related Link: http://www.ieice.org/ken/paper/20070920JAxI/
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.