| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-09-07 10:00 耳分解を利用してst-edge-ordering問題を解く自己安定分散アルゴリズムについて ○片山喜章・比嘉 臣・金 鎔煥（名工大）  COMP2023-9 |
|
| 抄録 | （和） | 本報告では，任意の2-辺連結グラフ$G=(V,E)$上で耳分解を利用して st-edge-ordering 問題を$mathrm{O}(|E|)$ラウンドで解く自己安定分散アルゴリズムを提案する． st-edge-ordering 問題とは，$G=(V,E)$と隣接頂点$s,tin V$が与えられたとき，辺$(s,t)in E$を除くすべての辺に番号を割り当てる問題で，頂点$s$に接続する辺のうちの1本に1を，$t$に接続する辺のうちの1本に$|E|-1$を割り当て，かつこれら以外のすべての辺は自分より番号が大きな辺と小さな辺の両方と隣接する（端点を共有する）よう番号付けなければならない． 耳分解とは$G=(V,E)$上の辺集合を$E=P_0cup P_1cup ldots cup P_x$（ただし$P_i(0leq ileq x)$は単純経路）である耳と呼ばれる単純経路$P_i$の系列に分割する問題で，ただし各$P_i(1leq i leq x)$の両端点が$P_0cup P_1cup cdotscup P_{i-1}$に含まれ，それ以外のノードは他の耳と頂点を共有しないよう分割する． 提案アルゴリズムは，著者らの知る限りいずれの問題に対しても初めての自己安定分散アルゴリズムであり，深さ優先探索問題を解く自己安定アルゴリズムなど複数の自己安定アルゴリズムの公平な合成により実現している． |
| （英） | In this report, a self-stabilizing distributed algorithm for solving st-edge-ordering problems on any 2-edge-connected graph is proposed. The algorithm solves the problem in $mathrm{O}(|E|)$ rounds. Given a 2-edge-connected graph $G=(V,E)$ and an edge $(s,t)in E$, an st-edge-ordering is a total order on the edge set $Ebackslash {(s,t)}$ such that every edge that is not incident $s,t$ has two neighbors whoes order is larger and smaller than it. An ear decomposition of a graph $G=(V,E)$ is a sequence $P_0, P_1, ldots, P_x$ of subgraphs of $G$ that partition $E$ such that every $P_i(1leq i leq x)$ is either intersects $P_0cup ldots cup P_{i-1}$ in its endpoints or a cycle that intersects $P_0 cup ldots cup P_{i-1}$ in a unique node (a endpoint). Each $P_i$ is called an ear. As far as the authors know, the proposed algorithm is the first self-stabilizing distributed algorithm solving ear decomposition and st-edge-ordering problems, and consists of several algorithms, including a DFS algorithm. |
|
| キーワード | （和） | 分散アルゴリズム / 自己安定 / 公平な合成 / 耳分解 / st-edge-ordering / / / |
| （英） | distributed algorithm / self-stabilization / fair composition / ear decomposition / st-edge-ordering / / / | |
| 文献情報 | 信学技報, vol. 123, no. 175, COMP2023-9, pp. 6-13, 2023年9月. | |
| 資料番号 | COMP2023-9 | |
| 発行日 | 2023-08-30 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-9 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2023-09-06 - 2023-09-07 |
| 開催地（和） | 大阪公立大学 |
| 開催地（英） | Osaka Metropolitan Univ. |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2023-09-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 耳分解を利用してst-edge-ordering問題を解く自己安定分散アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On a self-stabilizing distributed algorithm for st-edge-ordering problems using ear decomposition |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(2)（和/英） | 自己安定 / self-stabilization |
| キーワード(3)（和/英） | 公平な合成 / fair composition |
| キーワード(4)（和/英） | 耳分解 / ear decomposition |
| キーワード(5)（和/英） | st-edge-ordering / st-edge-ordering |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 片山 喜章 / Yoshiaki Katayama / カタヤマ ヨシアキ |
| 第1著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： NITech) |
| 第2著者 氏名（和/英/ヨミ） | 比嘉 臣 / Jin Higa / ヒガ ジン |
| 第2著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： NITech) |
| 第3著者 氏名（和/英/ヨミ） | 金 鎔煥 / Yonghwan Kim / キム ヨンファン |
| 第3著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： NITech) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-09-07 10:00:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-9 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.175 |
| ページ範囲 | pp.6-13 |
| ページ数 | 8 |
| 発行日 | 2023-08-30 (COMP) |
[研究会発表申込システムのトップページに戻る]