| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-02 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
A self-stabilizing algorithm for constructing a minimal reachable directed acyclic graph with two senders and two targets |
|
言語 |
en |
| その他のタイトル |
|
|
その他のタイトル |
A Self-Stabilizing Algorithm for Constructing a Minimal Reachable Directed Acyclic Graph with Two Senders and Two Targets |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Kim, Yonghwan
柴田, 将拡
Sudo Yuichi
Nakamura Junya
Katayama Yoshiaki
Masuzawa Toshimitsu
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In this paper, we introduce a new graph structure named an ST-reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability (i.e., a directed path exists) from every sender to every target. When an arbitrarily connected undirected graph G = (V,E) and two sets of the vertices, senders S (⊂V) and targets T (⊂V), are given, we consider the construction of a minimal ST-reachable DAG by changing some undirected edges to arcs and removing the remaining edges. In this paper, we present the necessary and sufficient condition under which a minimal ST-reachable DAG can be constructed when |S| ≤ 2 and |T| ≤ 2, and propose a self-stabilizing algorithm for constructing a minimal ST-reachable DAG (if it exists) when an arbitrarily connected undirected graph, S(|S| ≤ 2) and T (|T| ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of any ST-reachable DAG if the ST-reachable DAG of the given graph and two sets of vertices, S and T, do not exist. |
| 書誌情報 |
en : Theoretical Computer Science
巻 874,
p. 1-14,
発行日 2021-05-20
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.tcs.2021.05.005 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1879-2294 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0304-3975 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2021 Elsevier B.V. All rights reserved. |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Self-stabilization |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Directed acyclic graph |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Strong reachable DAG |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
RECN_2021-25.pdf (490 KB)
