Paper Info
Title
The binary network flow problem is logspace complete for P
Abstract
It is shown that the problem of whether the maximum flow in a given network exceeds a given natural number is logspace many-one complete for P if the edge capacities are presented in binary (even if the problem is restricted to acyclic graphs). This improves a result by Goldschlager et al. (1982) that this problem is logspace Turing complete for P.
Year
DOI
Venue
1990
10.1016/0304-3975(90)90101-M
Theor. Comput. Sci.
Keywords
DocType
Volume
binary network flow problem
Journal
75
Issue
ISSN
Citations 
3
Theoretical Computer Science
1
PageRank 
References 
Authors
0.47
3
2
Name
Order
Citations
PageRank
T. Lengauer111015.00
K. W. Wagner222418.58