積グラフの独立全域木について

• Item type: SIG Technical Reports(1)
• 公開日: 1996-01-22
• タイトル: 積グラフの独立全域木について
• タイトル / 言語: en
• タイトル: Independent Spanning Trees of Product Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): 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
• 著者名: 鮑豊; 五十嵐, 善英; 岩崎, 至宏; 小保方幸次
• 著者名(英): Feng, Bao; Yoshihide, Igarashi; Yukihiro, Iwasaki; Koji, Obokata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフGが頂点rを根とするn本の独立全域木が存在するならば，Gをrでのnチャネルグラフという．全ての頂点uに対して，Gがuでのnチャネルグラフならば，Gを単にnチャネルグラフという．独立全域木は，耐故障ブロードキャスティングにおいて重要である。Gが独立全域木についてある条件を満たすならば，well?formedという．本稿では，G_1がwell?formed n_1チャネルグラフでG_2がwell?formed n_2チャネルグラフならば，G_1×G_2は，well?formed (_1+n2_）チャネルグラフであることを示す．G_1のn_1本の独立全域木とG_2のn_2本の独立全域木からG_1×G_2のn_1+n_2本の独立全域木を構成することにより証明する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 for every vertex u, G is an n-channel graph at u. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. A graph G is said to be well-formed if G satisfy a certain condition about its independent spanning trees. In this paper we show that if G_1 is a well-formed n_1-channel graph and G_2 is a well-formed n_2-channel graph, then G_1×G_2 is a well-formed (n_1+n_2)-channel graph. We prove this fact by constructing n_1+n_2 independent spanning trees of G_1×G_2 satisfying the condition from n_1 independent spanning trees of G_1 and n_2 independent spanning trees of G_2.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 9(1995-AL-049), p. 25-32, 発行日 1996-01-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会