Some Complexity Results for the k-Splittable Flow Minimizing Congestion Problem
Open Access
- 1 January 2018
- journal article
- Published by Scientific Research Publishing, Inc. in Communications and Network
- Vol. 10 (01), 1-10
- https://doi.org/10.4236/cn.2018.101001
Abstract
In this paper, we mainly consider the complexity of the k-splittable flow minimizing congestion problem. We give some complexity results. For the k-splittable flow problem, the existence of a feasible solution is strongly NP-hard. When the number of the source nodes is an input, for the uniformly exactly k-splittable flow problem, obtaining an approximation algorithm with performance ratio better than (√5+1)/2 is NP-hard. When k is an input, for single commodity k-splittable flow problem, obtaining an algorithm with performance ratio better than is NP-hard. In the last of the paper, we study the relationship of minimizing congestion and minimizing number of rounds in the k-splittable flow problem. The smaller the congestion is, the smaller the number of rounds.Keywords
This publication has 1 reference indexed in Scilit: