Minimal congestion trees

DOI10.1016/j.disc.2004.02.009zbMath1051.05032OpenAlexW1968079464MaRDI QIDQ1877665

Mikhail I. Ostrovskii

Publication date: 19 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.02.009

zbMATH Keywords

Cheeger constantisoperimetric dimensionminimal congestion spanning tree

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Related Items (18)

A Survey on Spanning Tree Congestion ⋮ Scatter search for the minimum leaf spanning tree problem ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Spanners of bounded degree graphs ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ On tree congestion of graphs ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Spanning tree congestion of \(k\)-outerplanar graphs ⋮ Minimum congestion spanning trees in planar graphs ⋮ Unnamed Item ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ Unnamed Item ⋮ On spanning tree congestion of graphs ⋮ On spanning tree congestion ⋮ Spanning tree congestion of the hypercube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On minimizing width in linear layouts
• On embedding graphs in trees
• Graphs with small bandwidth and cutwidth
• The cyclic cutwidth of trees
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Minimal-volume shadows of cubes
• Minimal-volume projections of cubes and totally unimodular matrices
• The congestion of \(n\)-cube layout on a rectangular grid
• A metric on the set of connected simple graphs of given order
• On the Cutwidth and the Topological Bandwidth of a Tree
• A polynomial algorithm for the min-cut linear arrangement of trees
• [https://portal.mardi4nfdi.de/wiki/Publication:4337503 Open problems of Paul Erd�s in graph theory]
• Eigenvalues of Graphs and Sobolev Inequalities
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
• Vojtěch Jarník's work in combinatorial optimization

This page was built for publication: Minimal congestion trees