Two Complexity Results on Spanning-Tree Congestion Problems

Sunny Atalig, Marek Chrobak, Christoph Dürr +4

In the spanning-tree congestion problem ($\mathsf{STC}$), we are given a graph $G$, and the objective is to compute a spanning tree of $G$ that minimizes the maximum edge congestio…