论文研究 k可分裂流最小化拥塞问题的一些复杂性结果

在本文中，我们主要考虑k可拆分流最小化拥塞问题的复杂性。 我们给出一些复杂性结果。 对于k可分裂的流动问题，可行的解决方案的存在强烈是NP难的。 当输入源节点的数目时，对于均匀可k分解的均匀流问题，获得性能比（√5+ 1）/ 2更好的近似算法是NP-难的。 当输入k时，对于单个商品k可分解流问题，获得一种性能比优于NP难的算法。 在本文的最后，我们研究了k可分裂流问题中最小化拥塞和最小轮数的关系。 拥塞越小，轮数越少。