| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-09-11 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Weighted nearest neighbor algorithms for the graph exploration problem on cycles |
|
言語 |
en |
| その他のタイトル |
|
|
その他のタイトル |
Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
宮野, 英次
Miyazaki, Shuichi
Yoshimuta, Takuro
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. We assume that all the unknown graphs are undirected and connected. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling a tour as short as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm to explore cycles is better than 1.25-competitive. |
|
言語 |
en |
| 書誌情報 |
en : Information Processing Letters
巻 110,
号 3,
p. 93-98,
発行日 2009-10-28
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.ipl.2009.10.013 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0020-0190 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1872-6119 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2009 Elsevier B.V. All rights reserved. |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
On-line algorithms |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Graph exploration problem |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Weighted nearest neighbor |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Competitive ratio |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10347482.pdf (157 KB)
