Parameterized complexity of the spanning tree congestion problem
From MaRDI portal
Publication:1759686
DOI10.1007/S00453-011-9565-7zbMATH Open1253.68163OpenAlexW2012899511WikidataQ59567562 ScholiaQ59567562MaRDI QIDQ1759686FDOQ1759686
Authors: Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen 
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
Recommendations
- Complexity results for the spanning tree congestion problem
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- On spanning tree congestion of graphs
- Spanning tree congestion of planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Introduction to algorithms.
- Graph minors. X: Obstructions to tree-decomposition
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graphs on surfaces
- Title not available (Why is that?)
- Planar Formulae and Their Uses
- Efficient Planarity Testing
- The Complexity of Multiterminal Cuts
- Title not available (Why is that?)
- Quickly excluding a planar graph
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners of bounded degree graphs
- Tree Spanners
- Tree spanners in planar graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Diameter and treewidth in minor-closed graph families
- Graph minors. XVI: Excluding a non-planar graph
- Local tree-width, excluded minors, and approximation algorithms
- On spanning tree congestion of graphs
- On spanning tree congestion
- Spanning tree congestion of the hypercube
- Linearity of grid minors in treewidth with applications through bidimensionality
- On tree congestion of graphs
- Minimum congestion spanning trees in planar graphs
- On tree width, bramble size, and expansion
- Spanners in Sparse Graphs
- Bidimensional Parameters and Local Treewidth
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tree spanners for bipartite graphs and probe interval graphs
- A simpler proof of the excluded minor theorem for higher surfaces
- Minimal congestion trees
- Complexity results for the spanning tree congestion problem
- Minimum congestion spanning trees of grids and discrete toruses
- A variation on the min cut linear arrangement problem
- Approximation of minimum weight spanners for sparse graphs
- Embedding grids in surfaces
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
Cited In (16)
- Spanning tree congestion of \(k\)-outerplanar graphs
- The minimum centroid branch spanning tree problem
- A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- The minimum stretch spanning tree problem for typical graphs
- Fixed-Parameter Tractability for Non-Crossing Spanning Trees
- Complexity results for the spanning tree congestion problem
- Optimality computation of the minimum stretch spanning tree problem
- Better hardness results for the minimum spanning tree congestion problem
- Completely independent spanning trees in (partial) \(k\)-trees
- Spanning tree congestion and computation of generalized Győri-Lovász partition
- A Survey on Spanning Tree Congestion
- On the parameterized complexity of spanning trees with small vertex covers
- Better hardness results for the minimum spanning tree congestion problem
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- On the extremal structure of an OSPF related cone
This page was built for publication: Parameterized complexity of the spanning tree congestion problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759686)
