The parallel complexity of finding a blocking flow in a 3-layer network (Q1119019)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The parallel complexity of finding a blocking flow in a 3-layer network |
scientific article; zbMATH DE number 4096778
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The parallel complexity of finding a blocking flow in a 3-layer network |
scientific article; zbMATH DE number 4096778 |
Statements
The parallel complexity of finding a blocking flow in a 3-layer network (English)
0 references
1989
0 references
A flow in a network with a source s and a sink t is a blocking flow if every path from s to t contains a saturated edge. The authors show that the problem of finding the lex-first blocking flow in an acyclic network is log-space complete for P even if the network is restricted to be a 3- layer network. Inspite of this the authors demonstrate that there is a random NC algorithm for finding an arbitrary blocking flow in a 3-layer network.
0 references
parallel complexity
0 references
blocking flows
0 references
P-completeness
0 references
random NC
0 references
