Presentation | 2022-12-13 [Short Paper] For Understanding the First Meeting Time of Multiple Random Walks with Different Transition Probabilities Nanami Tsuji, Yusuke Sakumoto, Hiroyuki Osaki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Random walks on graphs have been used in various graph algorithms, and its understanding is important to design an efficient rendezvous algorithm on graphs. We have focused the first meeting time of multiple random walks following different transition probabilities, and derived the spectral formula of the expected first meeting time. In this paper, we further analyze the derived spectral formula, and clarify the characteristics of the first meeting time. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Spectral Graph Theory / Rendezvous Search / Random Walk / First Meeting Time |
Paper # | IA2022-59 |
Date of Issue | 2022-12-05 (IA) |
Conference Information | |
Committee | IN / IA |
---|---|
Conference Date | 2022/12/12(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Higashi-Senda campus, Hiroshima Univ. |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
Chair | Kunio Hato(Internet Multifeed) / Tomoki Yoshihisa(Osaka Univ.) |
Vice Chair | Tsutomu Murase(Nagoya Univ.) / Yusuke Sakumoto(Kwansei Gakuin Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
Secretary | Tsutomu Murase(KDDI Research) / Yusuke Sakumoto(Nagaoka Univ. of Tech.) / Yuichiro Hei(NTT) / Hiroshi Yamamoto(NTT) |
Assistant | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamura(Fukuoka Univ.) / Ryo Nakamura(Univ. of Tokyo) |
Paper Information | |
Registration To | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | [Short Paper] For Understanding the First Meeting Time of Multiple Random Walks with Different Transition Probabilities |
Sub Title (in English) | |
Keyword(1) | Spectral Graph Theory |
Keyword(2) | Rendezvous Search |
Keyword(3) | Random Walk |
Keyword(4) | First Meeting Time |
1st Author's Name | Nanami Tsuji |
1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
2nd Author's Name | Yusuke Sakumoto |
2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
3rd Author's Name | Hiroyuki Osaki |
3rd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
Date | 2022-12-13 |
Paper # | IA2022-59 |
Volume (vol) | vol.122 |
Number (no) | IA-306 |
Page | pp.pp.60-63(IA), |
#Pages | 4 |
Date of Issue | 2022-12-05 (IA) |