**American Mathematical Society Translations - Series 2**

1994;
221 pp;
Hardcover

MSC: Primary 05; 68; 90;

**Print ISBN: 978-0-8218-7509-4
Product Code: TRANS2/158**

List Price: $108.00

AMS Member Price: $86.40

MAA Member Price: $97.20

**Electronic ISBN: 978-1-4704-3369-7
Product Code: TRANS2/158.E**

List Price: $101.00

AMS Member Price: $80.80

MAA Member Price: $90.90

# Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar, 1972–1990

Share this page *Edited by *
*A. K. Kelmans*

This is a collection of translations of a variety of papers on discrete mathematics by members of the Moscow Seminar on Discrete Mathematics. This seminar, begun in 1972, was marked by active participation and intellectual ferment. Mathematicians in the USSR often encountered difficulties in publishing, so many interesting results in discrete mathematics remained unknown in the West for some years, and some are unknown even to the present day. To help fill this communication gap, this collection offers papers that were obscurely published and very hard to find. Among the topics covered here are: graph theory, network flow and multicommodity flow, linear programming and combinatorial optimization, matroid theory and submodular systems, matrix theory and combinatorics, parallel computing, complexity of algorithms, random graphs and statistical mechanics, coding theory, and algebraic combinatorics and group theory.

#### Readership

Research mathematicians.

# Table of Contents

## Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar, 1972-1990

- Cover Cover11
- Title page v6
- Copyright page vi7
- Contents vii8
- Russian Contents ix10
- Preface xi12
- Approximate evaluation of a linear function at the vertices of the unit 𝑛-dimensional cube 116
- On the growth of coefficients in an integral linear aggregation 1126
- A fast algorithm for constructing a maximum flow through a network 2338
- On the extremality of the rank function of a connected semimodular lattice 3146
- On polynomial solvability conditions for the simplest plant location problem 3752
- Minimal mean weight cuts and cycles in directed graphs 4762
- An algorithm for determining a maximum packing of odd-terminus cuts, and its applications 5772
- Maximum- and minimum-cost multicommodity flow problems having unbounded fractionality 7186
- On a class of maximum multicommodity flow problems with integer optimal solutions 8196
- On edge mappings of graphs preserving subgraphs of a given type 101116
- On edge semi-isomorphisms of graphs induced by their isomorphisms 113128
- Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles 127142
- Nonseparating circuits and the planarity of graph-cells 141156
- Extremal sets and covering and packing problems in matroids 149164
- Optimal distribution sorting 175190
- Branching packing in weighted graphs 185200
- Non-3-crossing families and multicommodity flows 201216
- The vector shortest path problem in the 𝑙_{∞}-norm 207222
- Lower performance bounds for on-line algorithms in the simple two-dimensional rectangle packing problems 217232
- Back Cover Back Cover1239