お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2015-09-01 14:00
木においてDデーモン下で1-極大マッチングを求めるサイレントな匿名自己安定アルゴリズム
麻田優真大下福仁・○井上美智子奈良先端大COMP2015-20
抄録 (和) 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 / / / /  
文献情報 信学技報, vol. 115, no. 205, COMP2015-20, pp. 27-34, 2015年9月.
資料番号 COMP2015-20 
発行日 2015-08-25 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2015-20

研究会情報
研究会 COMP  
開催期間 2015-09-01 - 2015-09-01 
開催地(和) 信州大学 
開催地(英)  
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2015-09-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) 木において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  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第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)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2015-09-01 14:00:00 
発表時間 30 
申込先研究会 COMP 
資料番号 IEICE-COMP2015-20 
巻番号(vol) IEICE-115 
号番号(no) no.205 
ページ範囲 pp.27-34 
ページ数 IEICE-8 
発行日 IEICE-COMP-2015-08-25 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会