Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00246 Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem Yoshio Okamoto , Yota Otachi , Ryuhei Uehara , and Takeaki Uno Vol. 15, no. 6, pp. 727-751, 2011. Regular paper Abstract Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O∗(2n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lemmas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.
|
Published: October 2011. Reviewed: September 2011. Submitted: May 2011. Revised: October 2011. Accepted: October 2011. Final: October 2011. Communicated by Seok-Hee Hong |
Journal of Graph Algorithms and Applications |