Better hardness results for the minimum spanning tree congestion problem

DOI10.1007/978-3-031-27051-2_15arXiv2209.08219MaRDI QIDQ6091160

Marek Chrobak, Huong Luu

Publication date: 24 November 2023

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2209.08219

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Spanning tree congestion of \(k\)-outerplanar graphs
• Spanners in sparse graphs
• On spanning tree congestion of graphs
• An independent dominating set in the complement of a minimum dominating set of a tree
• 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
• 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

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