Parameterized complexity of the spanning tree congestion problem
type: Item
instance of: scholarly article
title: Parameterized complexity of the spanning tree congestion problem
zbMATH Open document ID: 1253.68163
author: Hans L. Bodlaender
author: Fedor V. Fomin
author: Petr A. Golovach
author: Yota Otachi
author: Erik Jan van Leeuwen
published in: Algorithmica
publication date: 2012-11-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6109465
zbMATH Keywords: spanning tree congestion
zbMATH Keywords: graph minor
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: apex graph
MaRDI profile type: Publication
full work available at URL: s00453-011-9565-7
OpenAlex ID: W2012899511
Wikidata QID: Q59567562
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: Tree spanners on chordal graphs: complexity and algorithms
cites work: Tree spanners for bipartite graphs and probe interval graphs
cites work: Tree Spanners
cites work: Minimum congestion spanning trees of grids and discrete toruses
cites work: Q3651735
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: The Complexity of Multiterminal Cuts
cites work: Bidimensional Parameters and Local Treewidth
cites work: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
cites work: Linearity of grid minors in treewidth with applications through bidimensionality
cites work: Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
cites work: Q5315023
cites work: Spanners in Sparse Graphs
cites work: Approximation of minimum weight spanners for sparse graphs
cites work: Diameter and treewidth in minor-closed graph families
cites work: Tree spanners in planar graphs
cites work: Spanners of bounded degree graphs
cites work: Embedding grids in surfaces
cites work: Local tree-width, excluded minors, and approximation algorithms
cites work: On tree width, bramble size, and expansion
cites work: Efficient Planarity Testing
cites work: On tree congestion of graphs
cites work: On spanning tree congestion of graphs
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Spanning tree congestion of the hypercube
cites work: Q3048571
cites work: Planar Formulae and Their Uses
cites work: On spanning tree congestion
cites work: Q5764885
cites work: Combinatorial Local Planarity and the Width of Graph Embeddings
cites work: Graphs on surfaces
cites work: Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
cites work: Minimal congestion trees
cites work: Minimum congestion spanning trees in planar graphs
cites work: Complexity Results for the Spanning Tree Congestion Problem
cites work: Q4708559
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Quickly excluding a planar graph
cites work: A variation on the min cut linear arrangement problem
cites work: A simpler proof of the excluded minor theorem for higher surfaces
DOI: 10.1007/S00453-011-9565-7
description: scientific article; zbMATH DE number 6109465