電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2017-03-07 14:50
探索者数最適なオンライングラフ探索アルゴリズム
八神貴裕山内由紀子来嶋秀治山下雅史九大
技報オンラインサービス実施中
抄録 (和) グラフ探索問題は、グラフ内を逃げ回る侵入者を複数の探索者によって発見する問題である.辺探索ゲームはオフラインかつ集中型のグラフ探索問題で,グラフ上のペブルゲームでモデル化される.このモデルでグラフGの探索に十分な最小の石の個数をes(G)で表す.オンラインかつ分散型のグラフ探索問題も研究が進んでおり,そこでは,問題はモバイルエージェントモデルを用いて定式化している.本稿では,新しいオンラインかつ分散型のモデルを提案する.本モデルでは,ポート番号,ホームベース,ホワイトボードといった,モバイルネットワークに用いられる人工的な機構を一切仮定しない.本モデルの下で,探索者数に関して最適,つまりes(G)人の探索者でGを探索するオンライン探索アルゴリズムを提案する. 
(英) The graph search problem is the problem of searching for a mobile evader in a graph by mobile searchers.The edge search game is an offline and centralized version of this problem, and is modeled by a pebble game.Let es(G) be the minimum number of pebbles sufficient to search a graph G in this model.An online and distributed version of this problem has been investigated, and the problem is formalized by mobile agent model.We propose a new online and distributed setting.This setting does not assume artificial tools such that the port number, homebase or whiteboard in the graph.We propose an online search algorithm for es(G) searchers, i.e., this is optimal in terms of the number of searchers.
キーワード (和) グラフ探索問題 / オンラインアルゴリズム / 分散アルゴリズム / 非同期探索者 / 匿名グラフ / / /  
(英) graph search problem / online algorithm / distributed algorithm / asynchronous searchers / anonymous graph / / /  
文献情報 信学技報, vol. 116, no. 503, COMP2016-54, pp. 21-28, 2017年3月.
資料番号 COMP2016-54 
発行日 2017-02-28 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 COMP  
開催期間 2017-03-07 - 2017-03-07 
開催地(和) 南山大学 
開催地(英) Nanzan University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2017-03-COMP 
本文の言語 日本語 
タイトル(和) 探索者数最適なオンライングラフ探索アルゴリズム 
サブタイトル(和)  
タイトル(英) An Optimal Online Graph Search Algorithm in terms of the Number of Searchers 
サブタイトル(英)  
キーワード(1)(和/英) グラフ探索問題 / graph search problem  
キーワード(2)(和/英) オンラインアルゴリズム / online algorithm  
キーワード(3)(和/英) 分散アルゴリズム / distributed algorithm  
キーワード(4)(和/英) 非同期探索者 / asynchronous searchers  
キーワード(5)(和/英) 匿名グラフ / anonymous graph  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 八神 貴裕 / Takahiro Yakami / ヤカミ タカヒロ
第1著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ.)
第2著者 氏名(和/英/ヨミ) 山内 由紀子 / Yukiko Yamauchi / ヤマウチ ユキコ
第2著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ.)
第3著者 氏名(和/英/ヨミ) 来嶋 秀治 / Shuji Kijima / キジマ シュウジ
第3著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ.)
第4著者 氏名(和/英/ヨミ) 山下 雅史 / Masafumi Yamashita / ヤマシタ マサフミ
第4著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2017-03-07 14:50:00 
発表時間 30 
申込先研究会 COMP 
資料番号 IEICE-COMP2016-54 
巻番号(vol) IEICE-116 
号番号(no) no.503 
ページ範囲 pp.21-28 
ページ数 IEICE-8 
発行日 IEICE-COMP-2017-02-28 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会