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 the normal view instead:
scientific article; zbMATH DE number 4096778
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8456399440765381
0 references
0.8067935109138489
0 references
0.805142879486084
0 references
0.7699972987174988
0 references
