### ?

## О пересечении и симметрической разности семейств граничных классов графов для задач о раскраске и о хроматическом числе

Discrete Mathematics and Applications. 2012. Т. 24. № 2. С. 75-78.

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

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

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

Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...

Added: September 11, 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

Shitov Y., Information Processing Letters 2018 Vol. 135 P. 92-94

Let G = (V , E) be a finite simple graph. Recall that a proper coloring of G is a mapping φ : V → {1, . . . , k} such that every color class induces an independent set. Such a φ is called a semi-matching coloring if the union of any two consecutive ...

Added: September 26, 2018

Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31

Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...

Added: October 20, 2016

Malyshev D., Дискретная математика 2012 Т. 24 № 4 С. 91-103

В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и NP-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот,
доказывается достаточное условие ...

Added: May 17, 2013

Malyshev D., Razvenskaya O., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166

We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.
Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs. ...

Added: November 21, 2016

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

An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...

Added: June 6, 2012

Shitov Y., SIAM Journal on Optimization 2018 Vol. 28 No. 3 P. 2067-2072

Gouveia, Parrilo, and Thomas gave a description of certain rank functions of matrices in geometric terms, generalizing a celebrated result of Yannakakis on the nonnegative rank. We analyze the algorithmic complexity of their description using the results of Renegar on the first-order theory of the reals. This gives a proof that matrices whose positive semidefinite ...

Added: September 26, 2018

Gillis N., Shitov Y., Linear Algebra and its Applications 2019 Vol. 581 P. 367-382

The low-rank matrix approximation problem with respect to the entry-wise l∞-norm is the following: given a matrix M and a factorization rank r, find a matrix X whose rank is at most r and that minimizes max_i,j | M_ij − X_ij |. In this paper, we prove that the decision variant of this problem for ...

Added: November 11, 2020

Shitov Y., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77

We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...

Added: February 23, 2016

Malyshev D., Pardalos P. M., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...

Added: December 18, 2015

Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423-432

We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...

Added: April 23, 2018

Goldengorin B. I., Malyshev D., Pardalos P. M., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371

The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...

Added: June 23, 2013

Vassiliev V., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836

The local multiplicities of the caustics, the Maxwell sets, and the complex Stokes' sets in the spaces of versal deformations of Pham singularities (that is, of germs of holomorphic functions C^n --> C^1 which are expressed by the sums of degrees of the coordinate functions) are calculated ...

Added: December 27, 2017

Malyshev D., Siberian Electronic Mathematical Reports 2014 Vol. 11 P. 811-822

We obtain a complete complexity dichotomy for the edge 3- colorability within the family of hereditary classes defined by forbidden
induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures. ...

Added: April 7, 2014

Sirotkin D., Malyshev D., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766

The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree ...

Added: June 5, 2021

Shvydun S., Normative properties of multi-criteria choice procedures and their superpositions: II / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.

Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...

Added: October 20, 2015

Malyshev D., Journal of Applied and Industrial Mathematics 2017 Vol. 11 No. 1 P. 99-106

The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the ...

Added: February 13, 2017

Shitov Y., St Petersburg Mathematical Journal 2014 Vol. 26 No. 2 P. 216-228

The tropical arithmetic operations on R are defined as (a,b) -> min{a,b} and (a,b) -> a+b. We are interested in the concept of a semimodule, which is rather ill-behaved in tropical mathematics. In our paper we study the semimodules S in R^n having topological dimension two, and we show that any such S has always ...

Added: May 24, 2014

Shitov Y., Advances in Mathematics 2014 Vol. 254 P. 138-156

The tropical arithmetic operations on R are defined by a⊕b=min{a, b} and a⊗b=a+b. Let A be a tropical matrix and k a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^{m×k} and C∈R^{k×n} satisfying B⊗C=A. We show that no algorithm for TMF is likely to work in polynomial ...

Added: January 10, 2014

Malyshev D., Journal of Applied and Industrial Mathematics 2014 Vol. 8 No. 2 P. 245-255

The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem ...

Added: May 8, 2014