| 講演名 | 2015-06-13 st-orderingを利用した(1, 1)-極大DAG構成自己安定アルゴリズムについて 大野 陽香(名工大), 片山 喜章(名工大), 増澤 利光(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では, (s, t)-極大DAG という新たなネットワーク構造を導入し, 任意の連結ネットワーク上で(1, 1)-極大DAG 構成する自己安定アルゴリズムを提案する. (s, t)-極大DAG とは, 有向辺と無向辺の混在を許すグラフで, あらかじめ与えられたs個のノードをソース, t個のノードをシンクとし, 有向辺のみからなる有向辺を持たず, かつ方向づけられていない辺を一つでも方向付けると有向閉路を生じる. 提案アルゴリズムは, 任意の連結ネットワーク上に自己安定的に(1, 1)-極大DAG を構成するアルゴリズムであり, 2つの既知のアルゴリズムと3つの新規提案アルゴリズムを公平な合成によって合成することで実現する. |
| 抄録(英) | We propose a new network structure (s, t)-Maximal DAG and a self-stabilizing algorithm for constructing (1, 1)-Maximal DAG on any undirected connected graph. An (s, t)-Maximal DAG is a graph consistingof directed and undirected edges with given S sources and T sinks, which has no directed cycle (consisting only of directed edges) but creates a directed cycle by directing any edge in any direction. The proposed algorithm is obtained by fair composition of 2 known and 3 new algorithms composed by fair composition. |
| キーワード(和) | 自己安定 / DAG / (s, t)-極大DAG / 深さ優先木 / 関節点 |
| キーワード(英) | self-stabilization / DAG / (s, t)-Maximal DAG / DFS tree / articulation point |
| 資料番号 | COMP2015-12 |
| 発行日 | 2015-06-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2015/6/12(から2日開催) |
| 開催地（和） | 定山渓ビューホテル |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 和田 幸一(法政大) |
| 委員長氏名（英） | 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 / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | st-orderingを利用した(1, 1)-極大DAG構成自己安定アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On a Self-Stabilizing Algorithm for constructing a (1, 1)-Maximal Directed Acyclic Graph Using st-ordering |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自己安定 / self-stabilization |
| キーワード(2)（和/英） | DAG / DAG |
| キーワード(3)（和/英） | (s, t)-極大DAG / (s, t)-Maximal DAG |
| キーワード(4)（和/英） | 深さ優先木 / DFS tree |
| キーワード(5)（和/英） | 関節点 / articulation point |
| 第 1 著者 氏名（和/英） | 大野 陽香 / Haruka Ono |
| 第 1 著者 所属（和/英） | 名古屋工業大学(略称：名工大) Nagoya Institute of Technology(略称：NIT) |
| 第 2 著者 氏名（和/英） | 片山 喜章 / Yoshiaki Katayama |
| 第 2 著者 所属（和/英） | 名古屋工業大学(略称：名工大) Nagoya Institute of Technology(略称：NIT) |
| 第 3 著者 氏名（和/英） | 増澤 利光 / Toshimitsu Masuzawa |
| 第 3 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：OU) |
| 発表年月日 | 2015-06-13 |
| 資料番号 | COMP2015-12 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | COMP-84 |
| ページ範囲 | pp.115-122(COMP), |
| ページ数 | 8 |
| 発行日 | 2015-06-05 (COMP) |