No label defined (Q3320095)

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 3850794
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3850794

      Statements

      1983
      0 references
      oriented network
      0 references
      optimal flows
      0 references
      flow of minimal cost
      0 references
      shortest path
      0 references
      0 references
      Given is an oriented network \(G=(X,U)\) with a sink \(x_ 0\in X\). A non- negative number q(x) is associated with each node \(x\in X\backslash \{x_ 0\}\). The problem consists in finding a flow, \(\alpha\) : \(X\to R\), from \(x_ 0\) to other nodes (fulfilling their demands) minimizing the total cost: \[ F(\alpha)=\sum_{u\in U}\phi_ u(\alpha(u))\to \min. \] It is assumed that there are no constraints on arc capacities in the network G. The main result proved by the author is: if the cost functions \(\phi_ u(\cdot)\) are concave, non-decreasing functions then there is such a flow among the optimal flows that a part of the graph G generated by the arcs with positive flows is a tree with the root \(x_ 0\in X\). This result suggests a way of searching for a flow of minimal cost. It consists in building in G all possible trees with root \(x_ 0\) and determining a flow in each of them which is simple and univocal. Then a flow of minimal cost should be chosen. Such a procedure is the easier the smaller is the set of destinations \(Y=\{x\in X\), \(q(x)>0\}\). When \(| Y| =1\) the problem resolves itself into finding the shortest path from \(x_ 0\) to y with the lengths of arcs \(\ell(u)=\phi_ u(q(y))\), \(u\in U\). The author presents also a detailed algorithm for the case when \(| Y| =2\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references