ダウンロード数: 180
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
transinf.E92.D.1620.pdf | 338.73 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | MIYAZAKI, Shuichi | en |
dc.contributor.author | MORIMOTO, Naoyuki | en |
dc.contributor.author | OKABE, Yasuo | en |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 森本, 尚之 | ja |
dc.contributor.alternative | 岡部, 寿男 | ja |
dc.contributor.alternative | Miyazaki, Shuichi | en |
dc.contributor.alternative | Morimoto, Naoyuki | en |
dc.contributor.alternative | Okabe, Yasuo | en |
dc.date.accessioned | 2017-08-31T01:41:02Z | - |
dc.date.available | 2017-08-31T01:41:02Z | - |
dc.date.issued | 2009-09-01 | - |
dc.identifier.issn | 0916-8532 | - |
dc.identifier.uri | http://hdl.handle.net/2433/226939 | - |
dc.description.abstract | 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 ν, then it learns information on nodes and edges adjacent to ν. The searcher must decide which node to visit next depending on partial and incomplete information of the graph that it has gained in its searching process. The goodness of the algorithm is evaluated by the competitive analysis. If input graphs to be explored are restricted to trees, the depth-first search always returns an optimal tour. However, if graphs have cycles, the problem is non-trivial. In this paper we consider two simple cases. First, we treat the problem on simple cycles. Recently, Asahiro et al. proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant ε. In this paper, we give an optimal online algorithm for this problem; namely, we give a $frac{1+sqrt{3}}{2}(simeq1.366)$-competitive algorithm, and prove that there is no $(frac{1+sqrt{3}}{2}-epsilon)$-competitive algorithm for any positive constant ε. Furthermore, we consider the problem on unweighted graphs. We also give an optimal result; namely we give a 2-competitive algorithm and prove that there is no (2-ε)-competitive online algorithm for any positive constant ε. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Institute of Electronics, Information and Communications Engineers (IEICE) | en |
dc.publisher.alternative | 電子情報通信学会 | ja |
dc.rights | © 2009 The Institute of Electronics, Information and Communication Engineers | en |
dc.subject | the graph exploration problem | en |
dc.subject | online algorithm | en |
dc.subject | competitive analysis | en |
dc.title | The Online Graph Exploration Problem on Restricted Graphs | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | IEICE Transactions on Information and Systems | en |
dc.identifier.volume | E92-D | - |
dc.identifier.issue | 9 | - |
dc.identifier.spage | 1620 | - |
dc.identifier.epage | 1627 | - |
dc.relation.doi | 10.1587/transinf.E92.D.1620 | - |
dc.textversion | publisher | - |
dc.address | Kyoto University | en |
dc.address | Kyoto University | en |
dc.address | Kyoto University | en |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。