WEKO3
アイテム
Independent Spanning Trees of Product Graphs and Their Construction
https://ipsj.ixsq.nii.ac.jp/records/33746
https://ipsj.ixsq.nii.ac.jp/records/3374652ae2517-d968-40db-b342-20b4306cbd69
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1996 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1996-05-23 | |||||||
タイトル | ||||||||
タイトル | Independent Spanning Trees of Product Graphs and Their Construction | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Independent Spanning Trees of Product Graphs and Their Construction | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属 | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属 | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属 | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science Gunma University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science Gunma University | ||||||||
著者名 |
Koji, Obokata
× Koji, Obokata
|
|||||||
著者名(英) |
Koji, Obokata
× Koji, Obokata
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | SUMMARY A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r A graph G is called an n-Channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G_1 is an n_1-channel graph and G_2 is an n_2-channel graph then G_1×G_2 is an(n_1+n_2)-channel graph. We prove this fact by constructing n_1+n_2 independent spanning trees of G_1×G_2 from n_1 independent spanning trees of G_1 and n_2 independent spanning trees of G_2. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | SUMMARY A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r A graph G is called an n-Channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G_1 is an n_1-channel graph and G_2 is an n_2-channel graph, then G_1×G_2 is an(n_1+n_2)-channel graph. We prove this fact by constructing n_1+n_2 independent spanning trees of G_1×G_2 from n_1 independent spanning trees of G_1 and n_2 independent spanning trees of G_2. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN10505667 | |||||||
書誌情報 |
情報処理学会研究報告数理モデル化と問題解決(MPS) 巻 1996, 号 46(1996-MPS-007), p. 13-18, 発行日 1996-05-23 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |