講演名 | 2015-09-01 木においてDデーモン下で1-極大マッチングを求めるサイレントな匿名自己安定アルゴリズム 麻田 優真(奈良先端大), 大下 福仁(奈良先端大), 井上 美智子(奈良先端大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | We propose a silent self-stabilizing 1-maximal matching algorithm for anonymous trees under a distributed unfair daemon. Previously, we proposed a silent self-stabilizing 1-maximal matching algorithm with step step complexity of $O(e)$ for any anonymous networks without a cycle with length of a multiple of 3 under a central unfair daemon, where e is the number of edges. The step complexity of the proposed algorithm in this work is $O(n)$ moves where n is the number of nodes. That is, we relax the daemon to distributed daemon while preserving the step complexity but restricting the network topology to trees. |
抄録(英) | We propose a silent self-stabilizing 1-maximal matching algorithm for anonymous trees under a distributed unfair daemon. Previously, we proposed a silent self-stabilizing 1-maximal matching algorithm with step step complexity of $O(e)$ for any anonymous networks without a cycle with length of a multiple of 3 under a central unfair daemon, where e is the number of edges. The step complexity of the proposed algorithm in this work is $O(n)$ moves where n is the number of nodes. That is, we relax the daemon to distributed daemon while preserving the step complexity but restricting the network topology to trees. |
キーワード(和) | 分散アルゴリズム / 自己安定 / グラフ理論 / マッチング問題 |
キーワード(英) | distributed algorithm / self-stabilization / graph theory / matching problem |
資料番号 | COMP2015-20 |
発行日 | 2015-08-25 (COMP) |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2015/9/1(から1日開催) |
開催地(和) | 信州大学 |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 和田 幸一(法政大) |
委員長氏名(英) | Koichi Wada(Hosei Univ.) |
副委員長氏名(和) | 増澤 利光(阪大) |
副委員長氏名(英) | Toshimitsu Masuzawa(Osaka Univ.) |
幹事氏名(和) | 亀井 清華(広島大) / 古賀 久志(電通大) |
幹事氏名(英) | Sayaka Kamei(Hiroshima Univ.) / Hisashi Koga(Univ. of Electro-Comm.) |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
---|---|
本文の言語 | ENG-JTITLE |
タイトル(和) | 木においてDデーモン下で1-極大マッチングを求めるサイレントな匿名自己安定アルゴリズム |
サブタイトル(和) | |
タイトル(英) | A Silent Anonymous Self-Stabilizing Algorithm to Construct 1-Maximal Matching under the Distributed Daemon in Trees |
サブタイトル(和) | |
キーワード(1)(和/英) | 分散アルゴリズム / distributed algorithm |
キーワード(2)(和/英) | 自己安定 / self-stabilization |
キーワード(3)(和/英) | グラフ理論 / graph theory |
キーワード(4)(和/英) | マッチング問題 / matching problem |
第 1 著者 氏名(和/英) | 麻田 優真 / Yuma Asada |
第 1 著者 所属(和/英) | 奈良先端科学技術大学院大学(略称:奈良先端大) Nara Institute of Science and Technology(略称:NAIST) |
第 2 著者 氏名(和/英) | 大下 福仁 / Fukuhito Ooshita |
第 2 著者 所属(和/英) | 奈良先端科学技術大学院大学(略称:奈良先端大) Nara Institute of Science and Technology(略称:NAIST) |
第 3 著者 氏名(和/英) | 井上 美智子 / Michiko Inoue |
第 3 著者 所属(和/英) | 奈良先端科学技術大学院大学(略称:奈良先端大) Nara Institute of Science and Technology(略称:NAIST) |
発表年月日 | 2015-09-01 |
資料番号 | COMP2015-20 |
巻番号(vol) | vol.115 |
号番号(no) | COMP-205 |
ページ範囲 | pp.27-34(COMP), |
ページ数 | 8 |
発行日 | 2015-08-25 (COMP) |