Titlebook: Operations Research and Discrete Analysis; Alekseĭ D. Korshunov Book 1997 Springer Science+Business Media Dordrecht 1997 Boolean function.

DEI

effrontery

Operations and Isometric Embeddings of Graphs Related to the Metric Prolongation Property,ies of the locally-isometric embeddings. In the present paper, we continue the study of the MPP for finite graphs [1 – 5]. Some operations invariant with respect to the MPP are considered whose application simplifies the study of the MPP for certain classes of graphs. A theorem is proved on the isom

同步左右

继承人

On the Complexity of Realization of Boolean Functions by Circuits Over an Infinite Basis,ean functions, i.e.,the functions taking the value 1 only at pairwise incomparable tuples. It is shown thatas . → ∞ the complexity of realization of a linear function of . arguments over thebasis . grows at least as (./ log .).. It is established that the maximal complexity of realization of Boolean

委派

irradicable

Lower Bounds in the Problem of Choosing an Optimal Composition of a Two-Level System of Technical Td. These bounds are constructed by using Lagrangian relaxations. Two bounds are obtained as a result of relaxing two different groups of restrictions. It is shown that these bounds can be found in polynomial time. For incomparable bounds, domination areas are identified.

生气地

floaters

A Vertex Variant of the Kleitman-West Problem,the nth layer lying at distance 2 from . (i.e., in the frontier of .). Our main results are lower and upper bounds on the ratio of the size of the frontier to the size of the set and exact formulas for the size of the boundaries of ideals.

忘川河

On Comparison Between the Sizes of Read-,-Times Branching Programs,2, there exist a natural number .. and a sequence of Boolean functions such that the complexity of computation of every function of this sequence by read-.-times branching programs in an exponential number of times exceeds the complexity of computation of the same function by read-s . -times branchi

Commemorate

Some Optimization Problems of Scheduling the Transmission of Messages in a Local Communication Netwcoloring of the edges in a directed multigraph with the least possible number of colors. Two algorithms for the latter problem are presented. The term “mixed coloring” means that some of the edges can be splitted into two parts and be colored in two colors so that the number of the color of the firs