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

      0 references
      1988
      0 references
      nonnegative lower capacities
      0 references
      unbounded upper capacities
      0 references
      acyclic digraph
      0 references
      min flow
      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

      Identifiers