Complexity Results for the Spanning Tree Congestion Problem
From MaRDI portal
Publication:3057608
DOI10.1007/978-3-642-16926-7_3zbMath1308.68067OpenAlexW2150917267WikidataQ59567662 ScholiaQ59567662MaRDI QIDQ3057608
Yota Otachi, Erik Jan van Leeuwen, Hans L. Bodlaender
Publication date: 16 November 2010
Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_3
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A Survey on Spanning Tree Congestion, Better hardness results for the minimum spanning tree congestion problem, Spanners of bounded degree graphs, Parameterized complexity of the spanning tree congestion problem, Spanning tree congestion of \(k\)-outerplanar graphs, Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree spanners for bipartite graphs and probe interval graphs
- 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
- Graph minors. X: Obstructions to tree-decomposition
- A partial k-arboretum of graphs with bounded treewidth
- Minimal congestion trees
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners in Sparse Graphs
- Minimum congestion spanning trees of grids and discrete toruses
- A variation on the min cut linear arrangement problem
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Efficient Planarity Testing
- Tree Spanners
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Tree spanners in planar graphs
