Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
DOI10.1007/978-3-642-20877-5_44zbMath1331.68094OpenAlexW1489598663MaRDI QIDQ5892589
Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yota Otachi
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_44
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Spanning tree congestion of \(k\)-outerplanar graphs
- Exact exponential algorithms.
- On tree congestion of graphs
- Minimum congestion spanning trees in planar graphs
- On spanning tree congestion of graphs
- On spanning tree congestion
- Spanning tree congestion of the hypercube
- Minimal congestion trees
- Algorithmic graph theory and perfect graphs
- Quasi-threshold graphs
- Upper bounds to the clique width of graphs
- Spanning tree congestion of rook's graphs
- Complexity Results for the Spanning Tree Congestion Problem
- Fourier meets M\"{o}bius: fast subset convolution
- Minimum congestion spanning trees of grids and discrete toruses
- A variation on the min cut linear arrangement problem
- Computing the Minimum Fill-In is NP-Complete
- Graph Classes: A Survey
This page was built for publication: Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
