Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00246
Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
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.
|
Submitted: May 2011.
Reviewed: September 2011.
Revised: October 2011.
Accepted: October 2011.
Final: October 2011.
Published: October 2011.
Communicated by
Seok-Hee Hong
|
Journal Supporters
|