Recognizing hidden bicircular networks

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38) Deterministic network models in operations research (90B10) Linear programming (90C05) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

A generalized network flow problem is a linear program \(\min\{cx\mid Ax=b,\;x\geq 0\}\), where the matrix \(A\) has at most 2 nonzero entries in each column. The authors present a polynomial-time algorithm for transforming an \(m\times n\) matrix \(A\) of full rank into the constraint matrix of a generalized network flow problem provided there exists an underlying bicircular generalized network \(N\) whose generalized incidence matrix can be obtained from \(A\) by elementary row operations and nonzero column scaling. A bicircular generalized network is a weighted digraph having no cycle in which the product of the weights of forward arcs equals the product of the weights of backward arcs. Such a transformation is useful because generalized network flow problems can be solved much faster than regular linear programs. In this paper, the underlying graph \(G\) of \(N\) is constructed using an algorithm with worst-case complexity \(m^ 2 n^ 2\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Recognizing hidden bicircular networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208462)