Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E79-ANo.4pp.448-451 Publication Date: 1996/04/25 Online ISSN: DOI: Print ISSN: 0916-8508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: network flow, NP-completeness,
Full Text: PDF>>
Summary: An s-t flow in a directed network is called uncontrollable, when the flow is representable as a positive sum of elementary s-t path flows. In this paper, we discuss the problem Is a given flow uncontrollable?. We show that the problem is NP-complete.