1
$\begingroup$

Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ quantity of good from $s$ to $t_i$ along a path $P_i$. The problem is to find the set of path $P_i$ for each destination $t_i$ subject to edge capacity constraint. Is this problem NP_hard? Moreover, if each edge is associated with a cost $w_i$ and the problem is to find the set of paths $\{P_i\}$ of minimum total cost. How to develop algorithm solving this variant?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This problem is called single-source unsplittable flow problem [1]. This problem is NP-hard. The special case where there are only two nodes includes the bin packing problem.

  • [1]: J. M. Kleinberg, "Single-source unsplittable flow," Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 68-77.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .