講演抄録/キーワード |
講演名 |
2010-01-25 10:05
全域木混雑度問題の計算複雑性 ○大舘陽太(群馬大)・Hans L. Bodlaender(Utrecht Univ.) COMP2009-40 |
抄録 |
(和) |
本論文では,グラフの\emph{全域木混雑度}について研究する.初めに,与えられた次数制限されたグラフが,$k$以下の全域木混雑度を持つか否か決定する問題が,パラメータ$k$が固定されている場合は線形時間で解ける事を示す.次に,与えられたグラフが次数制限されない頂点を1個でも持つと,固定された$k \ge 10$に対して,グラフが$k$以下の全域木混雑度を持つか否か決定する問題が,NP完全である事を示す.さらに,$11/10$より良い近似比の解を求める事がNP困難である事も示す. |
(英) |
We study the computational complexity of determining the \emph{spanning tree congestion} of a graph. First, we show that the problem of determining whether a given graph has spanning tree congestion at most fixed $k$ can be solved in linear time for graphs of bounded degree. Next, we show that the problem becomes NP-complete for every fixed $k \ge 10$ if we allow only one vertex of unbounded degree in the input graphs. We also show that it is NP-hard to approximate the spanning tree congestion of such graphs within a factor better than $11/10$. |
キーワード |
(和) |
全域木混雑度 / 固定パラメータ容易性 / NP困難性 / / / / / |
(英) |
Spanning tree congestion / Fixed parameter tractability / NP-hardness / / / / / |
文献情報 |
信学技報, vol. 109, no. 391, COMP2009-40, pp. 9-16, 2010年1月. |
資料番号 |
COMP2009-40 |
発行日 |
2010-01-18 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-40 |