AbstractIt is known by Sahni that the integral flow problem with overlapped bundles is NP-complete. We show that this problem remains NP-complete even if the bundles are disjoint.
Selected references
- Sartaj Sahni. Computationally related problems. SIAM Journal on Computing, 3(4):262-279, December 1974.