Presentation | 2015-09-01 A Silent Anonymous Self-Stabilizing Algorithm to Construct 1-Maximal Matching under the Distributed Daemon in Trees Yuma Asada, Fukuhito Ooshita, Michiko Inoue, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | distributed algorithm / self-stabilization / graph theory / matching problem |
Paper # | COMP2015-20 |
Date of Issue | 2015-08-25 (COMP) |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2015/9/1(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Koichi Wada(Hosei Univ.) |
Vice Chair | Toshimitsu Masuzawa(Osaka Univ.) |
Secretary | Toshimitsu Masuzawa(Hiroshima Univ.) |
Assistant |
Paper Information | |
Registration To | Technical Committee on Theoretical Foundations of Computing |
---|---|
Language | ENG-JTITLE |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Silent Anonymous Self-Stabilizing Algorithm to Construct 1-Maximal Matching under the Distributed Daemon in Trees |
Sub Title (in English) | |
Keyword(1) | distributed algorithm |
Keyword(2) | self-stabilization |
Keyword(3) | graph theory |
Keyword(4) | matching problem |
1st Author's Name | Yuma Asada |
1st Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
2nd Author's Name | Fukuhito Ooshita |
2nd Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
3rd Author's Name | Michiko Inoue |
3rd Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
Date | 2015-09-01 |
Paper # | COMP2015-20 |
Volume (vol) | vol.115 |
Number (no) | COMP-205 |
Page | pp.pp.27-34(COMP), |
#Pages | 8 |
Date of Issue | 2015-08-25 (COMP) |