平面的グラフの基無指定k-分割問題に対する線形時間アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
グラフのk-分割問題は、(1)無向グラフG=(V, E)、(2)V∪Eの部分集合S、(3)互いに異なるSのk個の要素a_i(1≤i≤k)、(4)Σ^k_<i=1>n_i=|S|を満たす自然数n_1, n_2, ..., n_kとなる入力に対して、Sの分割S_1∪S_2∪...∪S_kで各S_iがa_iを含み、その要素数がn_iとなり、S_iを含む連結部分グラフG_iが存在してG_1, G_2, ...G_kが互いに辺独立となるものを求める問題である。また、入力の(2)のa_i(基と呼ぶ)をl(≤k)個だけ指定する問題を基l指定k-分割問題と呼ぶ。本稿では以下のことを示す。(1)Gが4-辺連結平面的グラフならばk≥2なるkに対して基1指定k-分割問題はO(|E|)時間で解ける。(2)Gが2-辺連結平面的グラフならば基1指定3-分割問題はO(|E|)時間で解ける。(3)Gが3-辺連結平面的グラフならば基1指定5-分割問題はO(|E|)時間で解ける。
1998-04-24

著者

関連論文

もっと見る

スポンサーリンク