Name
Title | ||
|---|---|---|
Hardness results and an exact exponential algorithm for the spanning tree congestion problem |
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 provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-20877-5_44 | Journal of Graph Algorithms and Applications |
Keywords | DocType | Volume |
tree congestion problem,non-sparse graph class,chain graph,linear-time algorithm,sparse graph class,new graph parameter,exact exponential algorithm,spanning tree congestion,hardness result,constant-factor approximation algorithm,chordal cographs,exact algorithm,split graph,spanning tree | Conference | 15 |
Issue | ISSN | Citations |
6 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 19 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshio Okamoto | 1 | 170 | 28.50 |
| Yota Otachi | 2 | 161 | 37.16 |
| Ryuhei Uehara | 3 | 528 | 75.38 |
| Takeaki Uno | 4 | 1319 | 107.99 |