Combinatorial analysis (nonnegative matrices, algorithmic problems) (Q1060220)

This survey is a continuation of the previous one by the same authors which was devoted to matrix problems, matroids and the theory of choice [Itogi Nauki Tekh., Ser. Teor. Veroyatn. Mat. Stat. Teor. Kibern. 18, 53- 93 (1981; Zbl 0475.05001); J. Sov. Math. 21, 910-937 (1983)]. It is based mainly on papers reviewed in Ref. Zh. ''Matematika'' during 1980-83. The sections are as follows: 1. Existence theorems for (0,1)-matrices: configurations in matrices, incidence matrices of block designs (called ''block-schemes'' in translation). 2. Extremal problems for (0,1)-matrices: coverings, depth. 3. Classification of (0,1)-matrices and graphs. 4. Matrices with nonnegative elements: Boolean, integral, real matrices; stochastic and doubly stochastic matrices, permanents (mentioning the proofs of van der Waerden's conjecture by Egorychev and Falikman). 5. Algorithms in algebraic problems: multiplication of matrices, complexity of algorithms, the algebraic assignment problem. 6. Selection problems. 7. Characterization of the classes P and NP. 8. Algorithms on graphs: matchings, paths, cycles; spanning trees, cutsets; colouring; verification of properties of graphs. The bibliography contains 248 items - more than 30 of them by authors from the USSR.