No label defined (Q3979312)

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

      Statements

      0 references
      26 June 1992
      0 references
      divergence function
      0 references
      packing
      0 references
      [For the entire collection see Zbl 0707.00019.] Let an oriented graph \(G=(V,E)\) with the set \(V\) of vertices and the set \(E\) of edges be given. We assign to every \(h\subseteq V\) the divergence function \(a_ h: E\to\mathbb{R}\) with the values \(a_ h(e)=1\) if \(i\in h\) and \(j\in\bar h\) (where \(\bar h=V-h\) and \(i\), \(j\) are the initial and terminal end-points of the edge \(e\in E\)), \(a_ h(e)=-1\) if \(i\in\bar h\) and \(j\in h\); otherwise \(a_ h(e)=0\) (\(\mathbb{R}\) is the set of real numbers). For given \(\ell: E\to\mathbb{R}\) and \(H\subseteq 2^ V=\{h: h\subseteq V\}\), we consider the problem consisting in the determination of the function \(y: H\to\mathbb{R}_ +\), for which \(\sum_{h\in H}y(h)a_ h\leq\ell\) (where \(\mathbb{R}_ +=\{x\in\mathbb{R}: x\geq 0\}\)). The function \(y\) is called a packing of divergence functions. This problem has essential relations to the problem of \textit{J. Edmond} and \textit{R. Giles} [Stud. integer Program., Proc. Workshop Bonn 1975, Ann. Discr. Math. 1 (1978; Zbl 0373.05040)]; it arises in case of consideration of optimality conditions for the last one. In the article in question, an efficient combinatorial algorithm for the construction of a solution of the packing problem (if it exists) is proposed. On the basis of this algorithm, a combinatorial criterion of the existence of a solution is proved.
      0 references

      Identifiers