Complexity results for the spanning tree congestion problem

DOI10.1007/978-3-642-16926-7_3MaRDI QIDQ3057608zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Parameterized complexity of 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
• Spanning tree congestion of planar graphs
• On spanning tree congestion of graphs

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A variation on the min cut linear arrangement problem
• Efficient Planarity Testing
• Graph minors. X: Obstructions to tree-decomposition
• Introduction to algorithms.
• Minimal congestion trees
• Minimum congestion spanning trees in planar graphs
• Minimum congestion spanning trees of grids and discrete toruses
• On spanning tree congestion
• On spanning tree congestion of graphs
• On tree congestion of graphs
• Spanners in Sparse Graphs
• Spanning tree congestion of the hypercube
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Tree Spanners
• Tree spanners for bipartite graphs and probe interval graphs
• Tree spanners in planar graphs
• Tree spanners on chordal graphs: complexity and algorithms

Cited in

(20)

• Spanning tree congestion of k-outerplanar graphs
• Parameterized complexity of the spanning tree congestion problem
• On spanning tree congestion of graphs
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• Finding minimum congestion spanning trees
• Approximating spanning tree congestion on graphs with polylog degree
• Minimum congestion spanning trees in bipartite and random graphs
• Better hardness results for the minimum spanning tree congestion problem
• Spanners of bounded degree graphs
• Spanning tree congestion of rook's graphs
• The complexity of spanning tree problems involving graphical indices
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• scientific article; zbMATH DE number 1418332 (Why is no real title available?)
• A Survey on Spanning Tree Congestion
• 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
• The complexity of the locally connected spanning tree problem
• Distance domination and amplifier placement problems
• Complexities of some interesting problems on spanning trees

This page was built for publication: Complexity results for the spanning tree congestion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057608)