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