Article citationsMore>>

Erlebach, T. and Hall, A. (2002) NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 6-8 January 2002.

has been cited by the following article:

• TITLE: Some Complexity Results for the k-Splittable Flow Minimizing Congestion Problem

  AUTHORS: Chengwen Jiao, Qi Feng, Weichun Bu

  KEYWORDS: k-Splittable Flow, Minimize Congestion, Minimize Number of Rounds, Complexity

  JOURNAL NAME: Communications and Network, Vol.10 No.1, December 13, 2017

  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.