講演抄録/キーワード |
講演名 |
2014-10-27 15:20
An Efficient Silent Self-Stabilizing Algorithm to Solve 1-Maximal Matching in Anonymous Networks ○Yuma Asada・Michiko Inoue(NAIST) DC2014-23 |
抄録 |
(和) |
We propose a new self-stabilizing 1-maximal matching algorithm which is silent and works for any anonymous networks without a cycle of a length of a multiple of 3 under a central unfair daemon. Let n and e be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is O(e) moves. Therefore, the complexity is O(n) moves for trees or rings whose length is not a multiple of 3. That is a significant improvement from the best existing results of O(n^4) moves for the same problem setting. |
(英) |
We propose a new self-stabilizing 1-maximal matching algorithm which is silent and works for any anonymous networks without a cycle of a length of a multiple of 3 under a central unfair daemon. Let n and e be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is O(e) moves. Therefore, the complexity is O(n) moves for trees or rings whose length is not a multiple of 3. That is a significant improvement from the best existing results of O(n^4) moves for the same problem setting. |
キーワード |
(和) |
分散アルゴリズム / 自己安定 / グラフ理論 / マッチング問題 / / / / |
(英) |
distributed algorithm / self-stabilization / graph theory / matching problem / / / / |
文献情報 |
信学技報, vol. 114, no. 280, DC2014-23, pp. 11-16, 2014年10月. |
資料番号 |
DC2014-23 |
発行日 |
2014-10-20 (DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
DC2014-23 |