文献

J-GLOBAL ID：201002252103639761   整理番号：10A0379340

有限グラフ上の被覆時間に対する恒等式の組合せ証明

Combinatorial Proof of the Identity for Cover Times on Finite Graphs

著者 (1件)： OHWA Takuya (Graduate School of Mathematics, Kyushu Univ.)
資料名： Interdisciplinary Information Sciences  (Interdisciplinary Information Sciences)
巻： 16  号： 1  ページ： 111-118 (J-STAGE)  発行年： 2010年 
JST資料番号： L2559A  ISSN： 1340-9050  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文は,[10]で得られた有限グラフ上のランダムウォークの被覆時間の確率密度に対する恒等式を,Moebius反転式と考えることによりその組合せ証明と拡大を与える。これに加え,多重ランダムウォークの被覆時間に対する類似の恒等式も求める。(翻訳著者抄録)

シソーラス用語： 有限性 ,  *被覆問題 ,  時間 ,  恒等式 ,  酔歩 ,  組合せ論 ,  証明 ,  *グラフ理論 ,  アルゴリズム ,  計算量 ,  無向グラフ ,  確率密度 ,  等価性 ,  スパンニング木 ,  反転
準シソーラス用語： 連結グラフ

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• [1] Aldous, D. J., and Fill, J., Reversible Markov chains and random walks on graphs, available via: http://stat-www.berkeley.edu/users/aldous/RWG/book.html (2001).
• [2] Alon, N., Avin, C., Kouký, M., Kozma, G., Lotker, Z., and Tuttle, M., Many Random Walks Are Faster Than One, available via: arXiv:math/0705.0467v2. (2007).
• [3] Broder, A., Karlin, A. R., Raghavan, P., and Upfal, E., “Trading space for time in undirected s-t connectivity,” SIAM J. Comput., 23: 324–334 (1994).
• [4] Levin, David A., Peres, Y., and Wilmer, Elizabeth L., Markov chains and mixing times, American Mathematical Society, Providence (2008).
• [5] Dembo, A., “Favorite Points, Cover Times and Fractals,” Lec. Notes Math., 1869: 3–101 (2005).

タイトルに関連する用語 (4件)： グラフ ,  恒等式 ,  組合せ ,  証明