<i>k</i>木における完全独立全域木について

スポンサーリンク

概要

• 論文の詳細を見る

• T1,T2 を連結グラフ G の二つの全域木とする.G の任意の 2 頂点 u,v に対して,T1 上の u-v パスと T2 上の u-v パスが,両端点以外に共通の頂点を持たないとき,T1 と T2 は互いに完全独立であるという.本論文では,以下の結果を証明した.(1) 与えられたグラフに 2 個の完全独立全域木が存在するかどうかを判定する問題は,入力をコーダルグラフに限定しても NP 完全である.(2) k ? 3 に対し,任意の k 木で少なくとも?(k+1)/2?個の互いに完全独立な全域木を構成可能である.(3) グラフ G で構成可能な完全独立全域木の最大数を CIST(G) と表す.?(k+1)/2? ? p ? k-1 を満たす任意の整数 p に対して CIST(G) = p となる k 木が存在する.

• 2010-09-15

著者

• 松下 正義

  群馬大学大学院工学研究科情報工学専攻

• 荒木 徹

  群馬大学大学院工学研究科情報工学専攻

• 荒木 徹

  岩手大学工学部情報システム工学科

• 荒木 徹

  群馬大学大学院工学研究科

• 松下 正義

  群馬大学大学院工学研究科 情報工学専攻

関連論文

• k木における完全独立全域木について
• k木における完全独立全域木について
• とびらの言葉
• 辺に故障のあるバブルソートグラフのhamiltonian laceability
• バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
• ハイパーキューブ族のネットワークにおける適応型故障診断について
• Bipartite permutation graphのL(2,1)ラベリング
• 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
• 局所完全ダイグラフの独立双方向支配集合問題について
• 完全独立全域木の十分条件について
• A-004 区間グラフの向き付けにおける双方向支配(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
• 完全独立全域木の十分条件について

もっと見る 閉じる

スポンサーリンク