| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-05-13 14:30 グラフ上の線形Cover Timeランダムウォーク実現の必要条件 ○野中良哲・小野廣隆・定兼邦彦・山下雅史（九大）  COMP2008-12 |
|
| 抄録 | （和） | 有限グラフ上のランダムウォークとは，グラフ上に置かれた粒子が，その隣接点へとある確率にしたがってランダムに遷移するモデルである. ランダムウォークの速さの指標として，cover timeがある.これはある頂点を出発した粒子が，全ての頂点を訪問するために要する遷移数の期待値である.本研究の目的は，グラフが与えられたときよりcover timeの小さなランダムウォークを設計することである．本発表では，n頂点からなるグラフに対してcover timeがO(n)であるランダムウォークを設計可能であるための必要条件を示す． |
| （英） | A random walk on a finite graph is a model that a token on a vertex repeatedly moves to an adjacent vertex randomly chosen according to some transition probability. The cover time of a random walk is a criterion of its speed, and roughly speaking, it is the expected number of steps in which the token visits all the vertices. Given a graph, we consider to design a fast random walk in terms of the cover time, by properly setting the transition probability. In this paper, we give necessary conditions for that the given graph has the cover time of O(n), where n is the number of vertices. | |
| キーワード | （和） | グラフ / ランダムウォーク / / / / / / |
| （英） | graph / random walk / / / / / / | |
| 文献情報 | 信学技報, vol. 108, no. 29, COMP2008-12, pp. 33-36, 2008年5月. | |
| 資料番号 | COMP2008-12 | |
| 発行日 | 2008-05-06 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-12 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-05-13 - 2008-05-13 |
| 開催地（和） | 九州産業大学 |
| 開催地（英） | Kyushu Sangyo University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-05-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフ上の線形Cover Timeランダムウォーク実現の必要条件 |
| サブタイトル（和） | |
| タイトル（英） | On Necessary Conditions of Linear Cover Time Random Walks |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | ランダムウォーク / random walk |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 野中 良哲 / Yoshiaki Nonaka / ノナカ ヨシアキ |
| 第1著者 所属（和/英） | 九州大学 (略称： 九大) Kyusyu University (略称： Kyusyu Univ) |
| 第2著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第2著者 所属（和/英） | 九州大学 (略称： 九大) Kyusyu University (略称： Kyusyu Univ) |
| 第3著者 氏名（和/英/ヨミ） | 定兼 邦彦 / Kunihiko Sadakane / サダカネ クニヒコ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyusyu University (略称： Kyusyu Univ) |
| 第4著者 氏名（和/英/ヨミ） | 山下 雅史 / Masafumi Yamashita / ヤマシタ マサフミ |
| 第4著者 所属（和/英） | 九州大学 (略称： 九大) Kyusyu University (略称： Kyusyu 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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-05-13 14:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-12 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.29 |
| ページ範囲 | pp.33-36 |
| ページ数 | 4 |
| 発行日 | 2008-05-06 (COMP) |
[研究会発表申込システムのトップページに戻る]