Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
スポンサーリンク
概要
- 論文の詳細を見る
8th Annual Conference on Theory and Applications of Medels of Computation, TAMC 2011, Tokyo, Japan, May 23-25, 2011.Spanning tree congestion is a relatively new graph parameter, whichhas been studied intensively. This paper studies the complexity of the problemto determine the spanning tree congestion for non-sparse graph classes, while itwas investigated for some sparse graph classes before. We prove that the problemis NP-hard even for chain graphs and split graphs. To cope with the hardnessof the problem, we present a fast (exponential-time) exact algorithm that runs inO ^∗(2^n) time, where n denotes the number of vertices. Additionally, we providea constant-factor approximation algorithm for cographs, and a linear-time algorithmfor chordal cographs.
- 2011-04-27
論文 | ランダム
- 工作の単元化についての研究
- 世代間交流とは何か
- 学校教育におけることば遊び--ことば遊びの実践と考察
- 北野天神縁起絵巻と孝養報恩 : 霊験譚「銅細工娘の段」の成立
- 急性心不全の初期対応--まず,最初に何をすべきか? 診断手順と治療のトリアージ (カラーで診る 臨床現場で役立つ 病棟必携!心不全診療マニュアル) -- (急性心不全)