### ?

## 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

Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in: <i>6th International Conference on Computers Communications and Control (ICCCC) 2016</i>. 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

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., Дискретная математика 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

Delong A., Osokin A., Isack H. et al., , in: <i>Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010)</i>. 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

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

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

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

Added: November 30, 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

Карташева А. А., Философские проблемы информационных технологий и киберпространства 2024

The problem of confirming the authenticity of works of art is especially acute in the digital environment. The issue of authentication is central to both intellectual property law and cultural communication strategies. Originality is a necessary parameter for a work to be recognized as original. Although the concept of «originality» is not enshrined in legal acts, it is an important element for the construction of «authenticity», which is often produced by «cultural intermediaries». The latter can be not only ...

Added: November 30, 2023

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

. 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

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., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801

For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...

Added: February 16, 2024

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

Babenko M. A., Goldberg A. V., Gupta A. ,. et al., ACM Transactions on Algorithms 2016 Vol. 13 No. 1 P. 16:1–16:17

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest- path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (l∞-norm) and simultaneously minimizing a constant number of lp-norms. Prior to this, an O(log n)- approximation algorithm was known [Cohen et al. 2003] only for ...

Added: January 12, 2017

Babenko M. A., Kociumaka T., Gawrychowski P. et al., , in: <i>Lecture Notes in Computer Science</i>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

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

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

Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221–228

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...

Added: June 23, 2013

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