| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-10 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
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. 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 as a short tour 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 is better than 1.25-competitive. |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
33rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2007, January 20-26, 2007, Harrachov, Czech Republic |
| 書誌情報 |
Lecture Notes in Computer Science
巻 4362,
p. 164-175,
発行日 2007
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-540-69507-3_13 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-540-69506-6 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-540-69507-3 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2007 Springer Berlin Heidelberg |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10347481.pdf (149 KB)
