文献

J-GLOBAL ID：201602220502479196   整理番号：16A0106777

2和音リングの独立スパニング木

Independent Spanning Trees of 2-Chordal Rings

著者 (1件)： HAMADA Yukihiro (Dep. of Electrical and Computer Engineering, National Inst. of Technol., Akashi Coll.)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E99.A  号： 1  ページ： 355-362 (J-STAGE)  発行年： 2016年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフG=(V,E)の2つのスパニング木T₁,T₂は,それらを同じ頂点に定着させた場合独立であり,rと言い,そして各頂点v∈Vで,T₁のrからvまでの経路およびT₂のrからvまでの経路は,rとvを除き共通の頂点および共通の端部を持たなかった。一般に,グラフG=(V,E)のスパニング木T₁,T₂,...,T_kはそれらがペアで独立である場合独立であった。グラフG=(V,E)は2-素リングと呼ばれそしてもしV={0,1,...,N-1}そしてE={(u,v)|[v-u]_N=1または[v-u]_N=d₁または[v-u]_N=d₂,2≦d₁2≦N/2}の場合CR(N,d₁,d₂)により表され,もしN≧8が偶数でそしてd₁≠N/2-1の場合CR(N,d₁,N/2)は5接続であった。著者らは,CR(N,d₁,N/2),N≧8で偶数そして2≦d₁≦[N/4],の5つの独立スパニング木を構築するためのアルゴリズムを提供した。(翻訳著者抄録)

シソーラス用語： *スパンニング木 ,  *音楽 ,  頂点 ,  経路 ,  端部 ,  独立性 ,  偶数 ,  *アルゴリズム ,  *グラフ理論
準シソーラス用語： *和音

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• [1] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, “Reliable broadcasting and secure distributing in channel networks,” IEICE Trans. Fundamentals, vol.E81-A, no.5, pp.796-806, May 1998.
• [2] S. Curran, O. Lee, and X. Yu, “Finding four independent trees,” SIAM J. Comput., vol.35, no.5, pp.1023-1058, 2006.
• [3] J. Cheriyan and S.N. Maheshwari, “Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs,” J. Algorithm., vol.9, no.4, pp.507-537, 1988.
• [4] A. Huck, “Independent trees in planar graphs,” Graphs and Combinatorics, vol.15, pp.29-77, 1999.
• [5] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, “Independent spanning trees of chordal rings,” Inform. Process. Lett., vol.69, no.3, pp.155-160, 1999.

タイトルに関連する用語 (2件)： 和音 ,  スパニング木