No label defined (Q3798455)
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 4064732
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4064732 |
Statements
1988
0 references
nonnegative lower capacities
0 references
unbounded upper capacities
0 references
acyclic digraph
0 references
min flow
0 references
0.8247774243354797
0 references
0.8212830424308777
0 references
0.8199052214622498
0 references
0.8169997334480286
0 references
[For the entire collection see Zbl 0639.00042.] The author considers a network flow problem with nonnegative lower capacities on the arcs and unbounded upper capacities. He shows that a feasible flow with minimum value can be computed in average time O(n 2log 2n) for an acyclic digraph. If the underlying digraph is strongly connected the construction of a min flow takes time O(n 2) in the worst case.
0 references