• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 24
Sort:
by name
by year
Article
Posypkin M., Kolpakov R. Optimization Letters. 2020. Vol. 14. No. 8. P. 2211-2226.

Increasing the number of computational cores is a primary way of achieving the high performance of contemporary supercomputers. However, developing parallel applications capable to harness the enormous amount of cores is a challenging task. It is very important to understand the principle limitations of the scalability of parallel applications imposed by the algorithm’s structure. The tree search addressed in this paper has an irregular structure unknown prior to computations. That is why such algorithms are challenging for parallel implementation especially on distributed memory systems. In this paper, we propose a parallel tree search algorithm aimed at distributed memory parallel computers. For this parallel algorithm, we analyze its scalability and show that it is close to the theoretical maximum. 

Added: Oct 30, 2020
Article
Malyshev D. Optimization Letters. 2021. Vol. 15. No. 2. P. 311-326.

The vertex colourability problem is to determine, for a given graph and a given natural k, whether it is possible to split the graph’s vertex set into at most k subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for {claw,butterfly}{claw,butterfly}-free graphs. A claw is the star graph with three leaves, a butterfly is obtained by coinciding a vertex in a triangle with a vertex in another triangle.

Added: Jan 6, 2021
Article
Gribanov D., Chirkov A. Optimization Letters. 2016. Vol. 10. No. 6. P. 1179-1189.

In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.

Added: Sep 12, 2016
1 2