Flow problem with multiplicative nodes

113 Views Asked by At

Is there any flow model that depicts flows in networks with multiplicative nodes?
By multiplicative node I mean a vertex $v$ such that:

$$k(v)*\sum_{e\in\delta^{in}(v)} f(e) = \sum_{e\in\delta^{out}(v)} f(e)$$

So it multiply incoming flow by $k=k(v)$

1

There are 1 best solutions below

0
On BEST ANSWER

In this case maximum flow problem is NP-hard. See textbook “Computers and intractability” by D. S. Johnson and M. Garey, p. 215, problem ND33, Integral flow with multipliers. Also you can see the proof of NP-hardness here.