An extension of the König-Egerváry property to node-weighted bidirected graphs (Q1108202)

Let \(G=(V,E)\) be a connected, finite, undirected graph without loops or multiple edges. If the number of nodes is n, let \(b=(b_ j)\) denote an n-vector of positive integral weights associated to the nodes. The author considers the linear program \[ CSP:\quad \max \sum^{n}_{i=1}b_ ix_ i, \] subject to \(x_ i+x_ j\leq 1\) for every edge [i,j]\(\in E\), and \(0\leq x_ i\leq 1\) for all \(i\in V\). In an earlier paper by \textit{J. M. Bourjolly, P. L. Hammer} and \textit{B. Simeone} [Math. Program. Study 22, 44-63 (1984; Zbl 0558.05054)] some results and two polynomial time recognition algorithms are given for CSP having an integral optimal solution (the König-Egerváry property). In the present paper this concept is extended to mixed graphs (having both directed and undirected edges) and bidirected graphs (whose edges have two heads, one head and one tail, or two tails).