全域木混雑度問題の計算複雑性
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,グラフの全域木混雑度について研究する.初めに,与えられた次数制限されたグラフが,k以下の全域木混雑度を持つか否か決定する問題が,パラメータkが固定されている場合は線形時間で解ける事を示す.次に,与えられたグラフが次数制限されない頂点を1個でも持つと,固定されたk≧10に対して,グラフがk以下の全域木混雑度を持つか否か決定する問題が,NP完全である事を示す.さらに,(11)/(10)より良い近似比の解を求める事がNP困難である事も示す.
- 2010-01-18
著者
関連論文
- グラフのデカルト積における木幅の下界
- グラフのデカルト積における木幅の下界
- 全域木混雑度問題の計算複雑性
- Spanning tree congestion of k-outerplanar graphs (コンピュテーション)