Parameterized complexity of the spanning tree congestion problem
From MaRDI portal
Publication:1759686
DOI10.1007/s00453-011-9565-7zbMath1253.68163OpenAlexW2012899511WikidataQ59567562 ScholiaQ59567562MaRDI QIDQ1759686
Erik Jan van Leeuwen, Hans L. Bodlaender, Fedor V. Fomin, Yota Otachi, Petr A. Golovach
Publication date: 21 November 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9565-7
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A Survey on Spanning Tree Congestion, Optimality computation of the minimum stretch spanning tree problem, Better hardness results for the minimum spanning tree congestion problem, A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs, Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition, Completely independent spanning trees in (partial) \(k\)-trees, The minimum stretch spanning tree problem for typical graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of minimum weight spanners for sparse graphs
- Tree spanners for bipartite graphs and probe interval graphs
- Linearity of grid minors in treewidth with applications through bidimensionality
- 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
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- A special planar satisfiability problem and a consequence of its NP- completeness
- Quickly excluding a planar graph
- A simpler proof of the excluded minor theorem for higher surfaces
- Graph minors. XVI: Excluding a non-planar graph
- Diameter and treewidth in minor-closed graph families
- Minimal congestion trees
- Embedding grids in surfaces
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners of bounded degree graphs
- Local tree-width, excluded minors, and approximation algorithms
- On tree width, bramble size, and expansion
- Complexity Results for the Spanning Tree Congestion Problem
- Spanners in Sparse Graphs
- Minimum congestion spanning trees of grids and discrete toruses
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- A variation on the min cut linear arrangement problem
- Planar Formulae and Their Uses
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Efficient Planarity Testing
- The Complexity of Multiterminal Cuts
- Tree Spanners
- Bidimensional Parameters and Local Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
- Tree spanners in planar graphs
