Dmitriy S. Malyshev

According to our database, Dmitriy S. Malyshev authored at least 44 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of five.
• Erdős number of three.

2024

On Δ-modular integer linear problems in the canonical form and equivalent problems.

Dmitry V. Gribanov, Ivan Shumilov, Dmitriy S. Malyshev, Panos M. Pardalos

J. Glob. Optim., March, 2024

Structured $(\min ,+)$-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems.

Dmitry V. Gribanov, I. A. Shumilov, Dmitriy S. Malyshev

Optim. Lett., January, 2024

Critical properties of bipartite permutation graphs.

Bogdan Alecu, Vadim V. Lozin, Dmitriy S. Malyshev

J. Graph Theory, January, 2024

2023

On linear algebraic algorithms for the subgraph matching problem and its variants.

Maxim D. Emelin, Ilya A. Khlystov, Dmitry S. Malyshev, Olga O. Razvenskaya

Optim. Lett., September, 2023

Combinatorics and Algorithms for Quasi-Chain Graphs.

Bogdan Alecu, Aistis Atminas, Vadim V. Lozin, Dmitriy S. Malyshev

Algorithmica, March, 2023

Faster Integer Points Counting in Parametric Polyhedra.

Dmitry V. Gribanov, Dmitriy S. Malyshev, Panos M. Pardalos, Nikolai Yu. Zolotykh

CoRR, 2023

2022

On partial descriptions of König graphs for odd paths and all their spanning supergraphs.

Dmitry B. Mokeev, Dmitry S. Malyshev

Optim. Lett., 2022

An intractability result for the vertex 3-colourability problem.

Dmitriy S. Malyshev, O. V. Pristavchenko

Optim. Lett., 2022

The number of maximal independent sets in trees with a given number of leaves.

Dmitrii S. Taletskii, Dmitriy S. Malyshev

Discret. Appl. Math., 2022

Structured (min, +)-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems.

Dmitry V. GRathoreribanov, Dmitriy S. Malyshev, I. A. Shumilov

CoRR, 2022

On a Simple Connection Between Δ-modular ILP and LP, and a New Bound on the Number of Integer Vertices.

Dmitry V. Gribanov, Dmitriy S. Malyshev, I. A. Shumilov

CoRR, 2022

Faster ILP Algorithms for Problems with Sparse Matrices and Their Applications to Multipacking and Multicover Problems in Graphs and Hypergraphs.

Dmitry V. Gribanov, Dmitry S. Malyshev

CoRR, 2022

Faster Exploration of Some Temporal Graphs.

Duncan Adamson, Vladimir V. Gusev, Dmitriy S. Malyshev, Viktor Zamaraev

Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks, 2022

2021

The computational complexity of weighted vertex coloring for P_{5, K_{2, 3}, K^{+_{2, 3}}}-free graphs.

Dmitriy S. Malyshev, Olga O. Razvenskaya, Panos M. Pardalos

Optim. Lett., 2021

The vertex colourability problem for claw, butterfly-free graphs is polynomial-time solvable.

Dmitriy S. Malyshev

Optim. Lett., 2021

Faster algorithm for counting of the integer points number in Δ-modular polyhedra.

Dmitry V. Gribanov, Dmitriy S. Malyshev

CoRR, 2021

2020

A polynomial-time algorithm of finding a minimum k-path vertex cover and a maximum k-path packing in some graphs.

Dmitry B. Mokeev, Dmitriy S. Malyshev

Optim. Lett., 2020

Independent domination versus weighted independent domination.

Vadim V. Lozin, Dmitriy S. Malyshev, Raffaele Mosca, Viktor Zamaraev

Inf. Process. Lett., 2020

2019

On the complexity of quasiconvex integer minimization problem.

Aleksandr Yu. Chirkov, Dmitry V. Gribanov, Dmitriy S. Malyshev, Panos M. Pardalos, Sergey I. Veselov, Nikolai Yu. Zolotykh

J. Glob. Optim., 2019

Integer Conic Function Minimization Based on the Comparison Oracle.

Dmitriy V. Gribanov, Dmitriy S. Malyshev

Proceedings of the Mathematical Optimization Theory and Operations Research, 2019

2018

FPT-algorithms for some problems related to integer programming.

Dmitry V. Gribanov, Dmitriy S. Malyshev, Panos M. Pardalos, Sergey I. Veselov

J. Comb. Optim., 2018

The computational complexity of dominating set problems for instances with bounded minors of constraint matrices.

Dmitriy S. Malyshev, Dmitry V. Gribanov

Discret. Optim., 2018

The weighted coloring problem for two graph classes characterized by small forbidden induced structures.

Dmitriy S. Malyshev

Discret. Appl. Math., 2018

2017

More results on weighted independent domination.

Vadim V. Lozin, Dmitriy S. Malyshev, Raffaele Mosca, Viktor Zamaraev

Theor. Comput. Sci., 2017

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems.

Marcel Turkensteen, Dmitriy S. Malyshev, Boris Goldengorin, Panos M. Pardalos

J. Glob. Optim., 2017

Polynomial-time approximation algorithms for the coloring problem in some cases.

Dmitriy S. Malyshev

J. Comb. Optim., 2017

The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs.

Dmitriy S. Malyshev

Graphs Comb., 2017

Two complexity results for the vertex coloring problem.

Dmitriy S. Malyshev, O. O. Lobanova

Discret. Appl. Math., 2017

Vertex coloring of graphs with few obstructions.

Vadim V. Lozin, Dmitriy S. Malyshev

Discret. Appl. Math., 2017

The computational complexity of three graph problems for instances with bounded minors of constraint matrices.

Dmitry V. Gribanov, Dmitriy S. Malyshev

Discret. Appl. Math., 2017

New Results on Weighted Independent Domination.

Vadim V. Lozin, Dmitriy S. Malyshev, Raffaele Mosca, Viktor Zamaraev

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

2016

Critical hereditary graph classes: a survey.

Dmitriy S. Malyshev, Panos M. Pardalos

Optim. Lett., 2016

A complexity dichotomy and a new boundary class for the dominating set problem.

Dmitriy S. Malyshev

J. Comb. Optim., 2016

Two cases of polynomial-time solvability for the coloring problem.

Dmitriy S. Malyshev

J. Comb. Optim., 2016

A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs.

Dmitriy S. Malyshev

Discret. Appl. Math., 2016

2015

The clique problem for graphs with a few eigenvalues of the same sign.

Dmitriy S. Malyshev, Panos M. Pardalos

Optim. Lett., 2015

A tolerance-based heuristic approach for the weighted independent set problem.

Boris I. Goldengorin, Dmitriy S. Malyshev, Panos M. Pardalos, Victor Zamaraev

J. Comb. Optim., 2015

The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs.

Dmitriy S. Malyshev

Discret. Math., 2015

The coloring problem for {P₅, P̅₅}-free graphs and {P₅, K_p-e}-free graphs is polynomial.

Dmitriy S. Malyshev, O. O. Lobanova

CoRR, 2015

A complexity dichotomy for the dominating set problem.

Dmitriy S. Malyshev

CoRR, 2015

2014

The coloring problem for classes with two small obstructions.

Dmitriy S. Malyshev

Optim. Lett., 2014

Boundary graph classes for some maximum induced subgraph problems.

Dmitriy S. Malyshev

J. Comb. Optim., 2014

2011

Boundary properties of graphs for algorithmic graph problems.

Nicholas Korpelainen, Vadim V. Lozin, Dmitriy S. Malyshev, Alexander Tiskin

Theor. Comput. Sci., 2011

2008

The Maximum Independent Set Problem in Planar Graphs.

Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy S. Malyshev, Martin Milanic

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008