The parallel complexity of finding a blocking flow in a 3-layer network

DOI10.1016/0020-0190(89)90225-1zbMath0669.68031OpenAlexW1981085297MaRDI QIDQ1119019

S. N. Maheshwari, Joseph Cheriyan

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90225-1

zbMATH Keywords

parallel complexityP-completenessblocking flowsrandom NC

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Theory of software (68N99)

Cites Work

• The maximum flow problem is log space complete for P
• An O(n2log n) parallel max-flow algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The parallel complexity of finding a blocking flow in a 3-layer network