The maximum flow problem is log space complete for P

Goldschlager L.M., Shaw R.A. and Staples J. (1982) The maximum flow problem is log space complete for P. Theoretical Computer Science, 21 1: 105-111. doi:10.1016/0304-3975(82)90092-5

Author Goldschlager L.M.
Shaw R.A.
Staples J.
Title The maximum flow problem is log space complete for P
Journal name Theoretical Computer Science   Check publisher's open access policy
ISSN 0304-3975
Publication date 1982-01-01
Sub-type Article (original research)
DOI 10.1016/0304-3975(82)90092-5
Volume 21
Issue 1
Start page 105
End page 111
Total pages 7
Language eng
Subject 1703 Computational Theory and Mathematics
Abstract The space complexity of the maximum flow problem is investigated. It is shown that the problem is log space complete for deterministic polynomial time. Thus the maximum flow problem probably has no algorithm which needs only O(logk n) storage space for any constant k. Another consequence is that there is probably no fast parallel algorithm for the maximum flow problem.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collections: Scopus Import
Scopus Import - Archived
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 70 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 73 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 26 Jul 2016, 13:10:45 EST by System User