Designing low-congestion sparse networks

研究了低拥塞稀疏网络的设计问题。特别地，我们研究了图上的一个最优化问题“生成树拥塞问题”的计算复杂性。我们展示了困难案例和简单案例之间的鲜明对比。我们还研究了该问题的参数复杂性，给出了该问题的一些二分法。我们的结果表明，在大多数情况下，这个问题确实很难解决。因此，我们设计了一些启发式算法和近似算法，并得到了一些部分结果。

We studied the problem of designing low-congestion sparse networks. Especially, we studied the computational complexity of an optimization problem on graphs called “the spanning tree congestion problem.” We presented sharp contrasts between hard cases and easy cases. We also investigated the parameterized complexity of the problem and gave some dichotomies for the problem. Our results imply the problem is really hard to solve for most of the cases. Thus we designed some heuristic and approximation algorithm and obtained some partial results.