### ?

## Special Issue on Computer Science Symposium in Russia

Vol. 64. Issue 1.
Springer, 2020.

Academic editor: Ф. В. Фомин, Podolskii V. V.

Under the general editorship: Ф. В. Фомин, Podolskii V. V.

This special issue of Theory of Computing Systems consists of extended journal papers originally presented at the 13th International Computer Science Symposium in Russia (CSR 2018) held on June 6–10, 2018 in Moscow, Russia. The event was hosted by National Research University Higher School of Economics and chaired by Vladimir V. Podolskii. Preliminary versions of these papers presented at the conference appeared in LNCS 10846. The Program Committee, chaired by Fedor V. Fomin, invited several authors to submit extended journal versions of their papers to this special issue. All submissions were reviewed in accordance with customary high standards.

Berlin : Springer, 2008

This book constitutes the refereed proceedings of the Third International Computer Science Symposium in Russia, CSR 2008, held in Moscow, Russia, June 7-12, 2008.
The 33 revised papers presented together with 5 invited papers and one opening lecture were carefully reviewed and selected from 103 submissions. All major areas in computer science are addressed. The theory ...

Added: October 30, 2013

Artamonov S., Babenko M. A., European Journal of Combinatorics 2018 P. 3-23

A perfect 2-matching in an undirected graph G=(V,E) is a function x:E→0,1,2 such that for each node v∈V the sum of values x(e) on all edges e incident to v equals 2. If supp(x)=e∈E∣x(e)≠0 contains no triangles then x is called triangle-free. Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. ...

Added: March 1, 2018

Cham : Springer, 2018

This book constitutes the refereed proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, held in Krems, Austria, in January/February 2018.
The 48 papers presented in this volume were carefully reviewed and selected from 97 submissions. They were organized in topical sections named: foundations of computer science; ...

Added: March 1, 2018

Rubtsov A. A., Vyalyi M., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.

We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...

Added: June 21, 2018

Berlin : Springer, 2012

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...

Added: October 30, 2013

Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...

Added: August 11, 2013

Switzerland : Springer, 2017

This book constitutes the refereed proceedings of the Third Russian Supercomputing Days, RuSCDays 2017, held in Moscow, Russia, in September 2017. The 41 revised full papers and one revised short paper presented were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on parallel algorithms; supercomputer simulation; high performance architectures, ...

Added: November 15, 2017

Mokeev D. B., Malyshev D., Optimization Letters 2020 Vol. 14 No. 6 P. 1317-1322

For a graph G and a positive integer k, a subset C of vertices of G is called a k-path vertex cover if C intersects all paths of k vertices in G. The cardinality of a minimum k-path vertex cover is denoted by β_{P_k}(G). For a graph G and a positive integer k, a subset ...

Added: March 12, 2020

Sirotkin D., Malyshev D., Journal of Applied and Industrial Mathematics 2018 Vol. 12 No. 4 P. 759-769

The 3-coloring problem for a given graph consists in verifying whether it is possible
to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete
complexity classification is known for this problem for the hereditary classes defined by triples of
forbidden induced subgraphs, each on at most 5 vertices. In this article, ...

Added: November 20, 2018

Delong A., Osokin A., Isack H. et al., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010). : San Francisco : IEEE, 2010. P. 2173-2180.

The α-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend α-expansion so that it can simultaneously optimize “label costs” as well. An energy with label ...

Added: October 18, 2017

Sirotkin D., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205

The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...

Added: July 2, 2018

Malyshev D., Journal of Applied and Industrial Mathematics 2012 Vol. 6 No. 1 P. 97-99

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other ...

Added: December 7, 2012

Malyshev D., Дискретная математика 2009 Т. 21 № 4 С. 129-134

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...

Added: November 25, 2012

Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.

The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...

Added: June 8, 2016

Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...

Added: April 7, 2014

Complexity function and complexity of validity of modal and superintuitionistic propositional logics

Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566-1595

We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...

Added: January 6, 2023

Malyshev D., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.

The coloring problem is studied in the paper for graph classes deﬁned by two small forbidden induced subgraphs. We prove some suﬃcient conditions for eﬀective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most ﬁve vertices except ...

Added: October 3, 2013

Popkov Y., Dubnov Y. A., Popkov A. Y., Automation and Remote Control 2018 Vol. 79 No. 11 P. 2038-2051

The direct and inverse projections (DIP) method was proposed to reduce the feature space to the given dimensions oriented to the problems of randomized machine learning and based on the procedure of “direct” and “inverse” design. The “projector” matrices are determined by maximizing the relative entropy. It is suggested to estimate the information losses by ...

Added: February 12, 2019

Babenko M. A., Kociumaka T., Gawrychowski P. et al., , in : Lecture Notes in Computer Science. Vol. 8486: Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching.: Springer, 2014. P. 30-39.

We revisit the problems of computing the maximal and the minimal non-empty suffixes of a substring of a longer text of length n, introduced by Babenko, Kolesnichenko and Starikovskaya [CPM’13]. For the minimal suffix problem we show that for any 1 ≤ τ ≤ logn there exists a linear-space data structure with(τ)query time and(nlogn/τ)preprocessing time. As a sample application, we show that ...

Added: June 24, 2014

Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...

Added: November 30, 2012

Malyshev D., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...

Added: November 25, 2012

Springer, 2019

16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...

Added: October 26, 2021

Alekseev V., Lozin V. V., Malyshev D. et al., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107

We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative ...

Added: November 7, 2012

Malyshev D., Journal of Applied and Industrial Mathematics 2020 Vol. 14 No. 4 P. 706-721

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...

Added: January 30, 2021