The maximum flow problem is log space complete for P
From MaRDI portal
Publication:1165000
DOI10.1016/0304-3975(82)90092-5zbMath0486.68035OpenAlexW2059378738MaRDI QIDQ1165000
Leslie M. Goldschlager, John Staples, Ralph A. Shaw
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90092-5
Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)
Related Items
An introduction to parallelism in combinatorial optimization, The parallel complexity of deadlock detection, Optimal edge ranking of trees in polynomial time, On the computational complexity of graph closures, Constructing a perfect matching is in random NC, The parallel complexity of finding a blocking flow in a 3-layer network, The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, On computing graph closures, Parallel approximation algorithms for bin packing, ReLU neural networks of polynomial size for exact maximum flow computation, Classifying the computational complexity of problems, The binary network flow problem is logspace complete for P, Parallel models of computation: An introductory survey, A P-complete graph partition problem, Processor-efficient implementation of a maximum flow algorithm, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Approximating the minimum-cost maximum flow is P-complete, A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model, Discrete and continuous models for partitioning problems, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs, Depth-first search is inherently sequential, Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems, A theory of complexity for continuous time systems, Flow in planar graphs with vertex capacities, A fast parallel algorithm for minimum-cost small integral flows
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\varepsilon\)-productions in context-free grammars
- Hierarchies of complete problems
- An observation on time-storage trade off
- Complete problems for deterministic polynomial time
- Linear programming is log-space hard for P
- A unified approach to models of synchronous parallel machines
