12 citations · 25 across the 6 of their papers we have counts for
6 papers
Critical properties of bipartite permutation graphs
Bogdan Alecu, Vadim Lozin, Dmitriy Malyshev
The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique- and rank-width of gra…
On the complexity of quasiconvex integer minimization problem
A. Yu. Chirkov, D. V. Gribanov, D. S. Malyshev +3
In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered in the p…
FPT-algorithms for some problems related to integer programming
D. V. Gribanov, D. S. Malyshev, P. M. Pardalos +1
In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices include…
More results on weighted independent domination
Vadim Lozin, Dmitriy Malyshev, Raffaele Mosca +1
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in th…
A complexity dichotomy for the dominating set problem
D. S. Malyshev
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.
The coloring problem for classes with two small obstructions
Dmitriy Malyshev
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of th…