グラフのあるk-分割問題に対する効率的なアルゴリズムについて

概要

論文の詳細を見る
グラフのk-要素分割問題は, (1) 連結無向グラフG=(V,E), (2) S⫅V∪E, (3) k個の異なる点または辺a_1,a_2,…,a_k∈S(各a_iを基と呼ぶ),(4)Σ^k_<i-=1>n_i=|S|となるk個の自然数n_1,n_2,…,n_kとなる入力に対して,Sの分割R_1,R_2,…,R_kで各R_iがa_iを含み,その要素数がn_iとなり,R_iを含む連結部分グラフG_iが存在してG_1,G_2,・・・,G_kが互いに辺独立となるものを求める問題である.また,入力(3)の条件を取り除いた問題を基無指定k-要素分割問題と呼ぶ.本論文では,k-要素分割可能であるための必要十分条件は入力グラフがk-辺連結であることを示し,k=2,3の場合には効率的に解けることを示す.また,基無指定k-要素分割問題に対して以下のことを示す.(1)Gが2-辺連結ならばO(|V|^2)時間で基無指定3-要素分割問題が解ける.(2)Gが4-辺連結ならばO(|V|√<|V|log|V|+|E>|)時間でk≧3に対する基無指定k-要素分割問題が解ける.
社団法人電子情報通信学会の論文
1995-12-25