On spanning tree congestion

DOI10.1016/j.disc.2009.01.012zbMath1213.05093OpenAlexW2107002514MaRDI QIDQ1044004

Dieter Rautenbach, Friedrich Regen, Christian Löwenstein

Publication date: 10 December 2009

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

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

zbMATH Keywords

embeddingcongestioncutwidthlayoutedge cutGomory-Hu tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

A Survey on Spanning Tree Congestion ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Spanning tree congestion of \(k\)-outerplanar graphs ⋮ Minimum congestion spanning trees in planar graphs ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem

Cites Work

• Unnamed Item
• Unnamed Item
• On tree congestion of graphs
• On embedding graphs in trees
• The cyclic cutwidth of trees
• Minimal congestion trees
• The congestion of \(n\)-cube layout on a rectangular grid
• Isoperimetric numbers of graphs
• Multi-Terminal Network Flows
• A homology theory for spanning tress of a graph