×

zbMATH — the first resource for mathematics

The maximum flow problem is log space complete for P. (English) Zbl 0486.68035

MSC:
68Q25 Analysis of algorithms and problem complexity
90B10 Deterministic network models in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen, I., A new parallel algorithm for network flow problems, (), 306-307
[2] Chen, Y.K.; Feng, T., A parallel algorithm for the maximum flow problem, Proc. 2nd sagamore computer conference on parallel processing, 60, (1973), Raquette Lake, NY
[3] Cook, S.A., An observation of time-storage trade off, J. comput. system sci., 9, 3, 308-316, (1974) · Zbl 0306.68026
[4] Dobkin, D.; Lipton, R.J.; Reiss, S., Linear programming is log-space hard for P, Information processing lett., 9, 2, 96-97, (1979) · Zbl 0402.68042
[5] Even, S., Graph algorithms, (1979), Pitman London · Zbl 0441.68072
[6] Galil, Z., Hierarchies of complete problems, Acta informat., 6, 77-88, (1976) · Zbl 0304.68044
[7] Goldschlager, L.M., A unified approach to models of synchronous parallel machines, Proc. 10th annual ACM symposium on theory of computing, 89-94, (1978) · Zbl 1282.68105
[8] Goldschlager, L.M., The monotone and planar circuit value problems are log space complete for P, SIGACT news, 9, 2, 25-29, (1977)
[9] Goldschlager, L.M., Ε-productions in context-free grammars, Acta informat, 16, 303-308, (1981) · Zbl 0452.68082
[10] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[11] Jones, N.D.; Laaser, W.T., Complete problems for deterministic polynomial time, Theoret. comput. sci., 3, 1, 105-117, (1976) · Zbl 0352.68068
[12] Kozen, D., Complexity of finitely presented algebras, Proc. 9th annual ACM symposium on theory of computing, 164-177, (1977)
[13] Ladner, R.E., The circuit value problem is log space complete for P, SIGACT news, 7, 1, 18-20, (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.