Independent Spanning Trees of Product Graphs and Their Construction
スポンサーリンク
概要
- 論文の詳細を見る
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_1xG_2 is an (n_1+n_2)-channel graph. We prove this fact by constructing n_1+n_2 independent spanning trees of G_1xG_2 from n_1 independent spanning trees of G_1 and n_2 independent spanning trees of G_2.
- 一般社団法人情報処理学会の論文
- 1996-05-23
著者
-
Bao F
National Univ. Sinpapore Singapore
-
Igarashi Yoshihide
Department of Computer Science, Gunma University
-
Obokata Koji
Department of Computer Science Gunma University
-
Iwasaki Yukihiro
Department of Computer Science Gunma University
-
Bao Feng
Department of Computer Science Gunma University
-
Obokata K
Univ. Auckland Auckland Nzl
-
Igarashi Y
Gunma Univ. Kiryu‐shi Jpn
-
Igarashi Yoshihide
Department Of Computer Science Gunma University
関連論文
- Information Disseminating Schemes and Their Fault Tolerance in Hypercubes
- A More Efficient Improvement of the Virtual Software Token Protocols (Fundamental Theories for Communications)
- Security Notes on Generalization of Threshold Signature and Authenticated Encryption(Information Security)
- Optimal Time Broadcasting Schemes in Faulty Star Graphs (Special Section on Discrete Mathematics and Its Applications)
- Reliable Broadcasting and Secure Distributing in Channel Networks(Special Section on Discrete Mathematics and Its Applications)
- Independent Spanning Trees of Product Graphs and Their Construction
- Independent Spanning Trees of Product Graphs and Their Construction
- Nonadaptive Fault-Tolerant File Transmission in Rotator Graphs (Special Section on Discrete Mathematics and Its Applications)
- Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults
- Broadcasting in Hypercubes with Randamly Distributed Byzantine Faults
- Embeddings of Hyper-Rings in Hypercubes
- REMARKS ON REAL-TIME DETERMINISTIC CONTEXT-FREE LANGUAGES(Mathematical Theories on Computing Schemes and Their Applications)
- Roughly Sorting: Sequential and Parallel Approach
- Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model (Special Issue on Selected Papers from LA Symposium)
- Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Ordersl(Foundations of Computer Science)
- Construction of Secret Key Exchange Spanning Trees by Random Deals of Cards on Hierarchical Structures (Special Section on Discrete Mathematics and Its Applications)
- Secure Multi-Party Computation over Networks(Special Issue on Algorithm Engineering : Surveys)
- Analysis of Some Lockout Avoidance Algorithms for the k-Exclusion Problem
- Roughly Sorting: A Generalization of Sorting