PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

New $(n,r)$-Arcs in PG$(2,17)$, PG$(2,19)$, and PG$(2,23)$
R. Daskalov and E. Metodieva
pp. 217–223

Abstract—An $(n,r)$-arc is a set of $n$ points of a projective plane such that some $r$ but no $r+1$ of them are collinear. The maximum size of an $(n,r)$-arc in PG$(2,q)$ is denoted by $m_r(2,q)$. In this paper a new $(95,7)$-arc, $(183,12)$-arc, and $(205,13)$-arc in PG$(2,17)$ are constructed, as well as a $(243,14)$-arc and $(264,15)$-arc in PG$(2,19)$. Likewise, good large $(n,r)$-arcs in PG$(2,23)$ are constructed and a table with bounds on $m_r(2,23)$ is presented. In this way many new $3$-dimensional Griesmer codes are obtained. The results are obtained by nonexhaustive local computer search.

Classification of Optimal $(v,4,1)$ Binary Cyclically Permutable Constant-Weight Codes and Cyclic $2$-$(v,4,1)$ Designs with $v\le 76$
T. Baicheva and S. Topalova
pp. 224–231

Abstract—We classify up to isomorphism optimal $(v,4,1)$ binary cyclically permutable constant-weight (CPCW) codes with $v\le 76$ and cyclic $2$-$(73,4,1)$ and $2$-$(76,4,1)$ designs. There is a one-to-one correspondence between optimal $(v,4,1)$ CPCW codes, optimal cyclic binary constant-weight codes with weight $4$ and minimum distance $6$, $(v,4;\lfloor (v-1)/12\rfloor)$ difference packings, and optimal $(v,4,1)$ optical orthogonal codes. Therefore, the classification of CPCW codes holds for them too. Perfect $(v,4,1)$ CPCW codes are equivalent to $(v,4,1)$ cyclic difference families, and thus $(73,4,1)$ cyclic difference families are classified too.

Method of Lyapunov Functions for Analysis of Absorption and Explosion in Markov Chains
P.-L. Chow and R. Z. Khasminskii
pp. 232–250

Abstract—The main goal of this paper is to derive some sufficient conditions for testing the absorption, explosion, and nonexplosion of time-inhomogeneous Markov chains with a countable state space. The method of Lyapunov functions is used for this purpose. Several theorems concerned with such sufficient conditions are proved for a general class of Markov chains. Then they are applied to some problems in time-inhomogeneous birth-death processes and branching processes.

On a Sequence of Random Distance Graphs Subject to the Zero-One Law
M. E. Zhukovskii
pp. 251–268

Abstract—It is known that an Erdős–Rényi random graph obeys a zero-one law for first-order properties. The study of these laws started in 1969 with the work of Yu.V. Glebskii, D.I. Kogan, M.I. Liogon'kii, and V.A. Talanov. We proved in our previous works that a random distance graph does not obey the zero-one law. In this paper a sequence of random distance graphs obeying the zero-one law is obtained.

Linear Algorithm for Selecting an Almost Regular Spanning Subgraph in an Almost Regular Graph
M. A. Babenko and T. A. Urbanovich
pp. 269–273

Abstract—We consider almost $d$-regular graphs, i.e., graphs having all vertex degrees equal to either $d$ or $d-1$. It is known that for each $d'\le d$ every $d$-regular graph contains an almost $d'$-regular spanning subgraph. We give an algorithm for selecting such a subgraph in optimal linear time.

The Tree Nearest on Average to a Given Set of Trees
K. Yu. Gorbunov and V. A. Lyubetsky
pp. 274–288

Abstract—We formulate the problem of constructing a tree which is the nearest on average to a given set of trees. The notion of “nearest” is formulated based on a conception of events such that counting their number makes it possible to distinguish each of the given trees from the desired one. These events are called divergence, duplication, loss, and transfer; other lists of events can also be considered. We propose an algorithm that solves this problem in cubic time with respect to the input data size. We prove correctness of the algorithm and a cubic estimate for its complexity.

Configuration of Overloaded Servers with Dynamic Routing
N. D. Vvedenskaya
pp. 289–303

Abstract—We consider overload of servers in a network with dynamic routing of messages. The system consists of $k$ servers and $l$ independent Poisson input flows. Messages from each flow are directed to $m$ servers, and each message is directed to a server that is the least loaded at the moment of its arrival. In such a system, configuration of overloaded servers depends on the intensity of input flows. A similar effect was considered in [1] for a system with another geometry.