Better hardness results for the minimum spanning tree congestion problem

DOI10.1007/s00453-024-01278-5MaRDI QIDQ6670816

M. Chrobak, Huong Luu

Publication date: 24 January 2025

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationcongestionspanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Spanning tree congestion of \(k\)-outerplanar graphs
• Spanners in sparse graphs
• On spanning tree congestion of graphs
• Designing multi-commodity flow trees
• Parameterized complexity of the spanning tree congestion problem
• Minimal congestion trees
• Spanning tree congestion of rook's graphs
• Complexity Results for the Spanning Tree Congestion Problem
• Spectral Sparsification of Graphs
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• The Complexity of Multiterminal Cuts
• Tree Spanners
• The complexity of scheduling TV commercials
• Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition
• A Survey on Spanning Tree Congestion
• A general framework for graph sparsification
• Term Rewriting and Applications
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• Tree spanners in planar graphs
• Better hardness results for the minimum spanning tree congestion problem

This page was built for publication: Better hardness results for the minimum spanning tree congestion problem