The maximum flow problem is log space complete for P

Goldschlager, Leslie M., Shaw, Ralph A. and Staples, John (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, Leslie M.
Shaw, Ralph A.
Staples, John
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-10-01
Year available 1982
Sub-type Article (original research)
DOI 10.1016/0304-3975(82)90092-5
Open Access Status DOI
Volume 21
Issue 1
Start page 105
End page 111
Total pages 7
Place of publication Amsterdam, Netherlands
Publisher Elsevier
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 UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import - Archived
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 66 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 26 Jul 2016, 13:10:45 EST by System User on behalf of Learning and Research Services (UQ Library)