| Item type |
SIG Technical Reports(1) |
| 公開日 |
2022-05-12 |
| タイトル |
|
|
タイトル |
2-連結グラフ上の2頂点対点素パスを構築する自己安定アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Self-Stabilizing Algorithm to Construct Node Disjoint Paths between Two Senders and Targets on a Biconnected Graph |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
名古屋工業大学大学院工学研究科工学専攻情報工学系プログラム |
| 著者所属 |
|
|
|
名古屋工業大学大学院工学研究科工学専攻情報工学系プログラム |
| 著者所属 |
|
|
|
名古屋工業大学大学院工学研究科工学専攻情報工学系プログラム |
| 著者所属(英) |
|
|
|
en |
|
|
Nagyoya Institute of Technology, Graduate School of Computer Science and Engineering |
| 著者所属(英) |
|
|
|
en |
|
|
Nagyoya Institute of Technology, Graduate School of Computer Science and Engineering |
| 著者所属(英) |
|
|
|
en |
|
|
Nagyoya Institute of Technology, Graduate School of Computer Science and Engineering |
| 著者名 |
北岡, 拓馬
金, 鎔煥
片山, 喜章
|
| 著者名(英) |
Takuma, Kitaoka
Yonghwan, Kim
Yoshiaki, Katayama
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本研究は 2-連結グラフにおける 2 頂点対点素パスの構築を考える．パスは送信ノード（始点）から受信ノード（終点）までのノード列で表し，任意の 2 本のパスにおいて含まれるノードが全て異なるとき，２本のパスを点素パスと呼ぶ．さらに，あるグラフとそれぞれ異なる 2 つの始点と２つの終点が与えられたとき，始点と終点をそれぞれ結ぶ 2 本のパスを 2 頂点対点素パスと呼ぶ．与えられたグラフが 2 連結である場合，2 つの始点及び終点がどの頂点であっても必ず 2 頂点対点素パスが存在することを示し，2-連結グラフ上で 2 頂点対点素パスを構築する自己安定アルゴリズムを提案する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A path is a sequence of consecutive nodes in the graph, and two paths are disjoint if the nodes included in the two paths are pairwise disjoint. In this paper, we consider the construction of two disjoint paths from a source node (called sender) to a target node (called target) when a graph and four different nodes, two senders and two targets, in the graph are given. We firstly show that the two disjoint paths between two senders and targets must exist if the given graph is biconnected (i.e., sufficient condition). Moreover, we introduce a self-stabilizing algorithm to construct the two disjoint paths between two senders and targets in the biconnected graph. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2022-AL-188,
号 6,
p. 1-8,
発行日 2022-05-12
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL22188006.pdf (2.5 MB)
