?
Construction of the solution of the Chinese Remainder Theorem for polynomials using the method of undetermined coefficients
P. 115-116.
Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
Добавлено: 18 декабря 2015 г.
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566-1595
Добавлено: 6 января 2023 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2012 Vol. 6 No. 1 P. 97-99
Добавлено: 7 декабря 2012 г.
Рубцов А. А., Вялый М. Н., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.
Добавлено: 21 июня 2018 г.
Шитов Я. Н., 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. ...
Добавлено: 23 февраля 2016 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Мокеев Д. Б., Малышев Д. С., Optimization Letters 2020 Vol. 14 No. 6 P. 1317-1322
Добавлено: 12 марта 2020 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
Задача о вершинной 3-раекраеке для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NР-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. ...
Добавлено: 2 июля 2018 г.
Алескеров Ф. Т., Мещерякова Н. Г., Швыдун С. В. и др., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
Добавлено: 8 июня 2016 г.
Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502
We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...
Добавлено: 11 августа 2013 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443
Добавлено: 24 сентября 2020 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Малышев Д. С., 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. © 2015 Elsevier B.V. All rights reserved. ...
Добавлено: 7 апреля 2014 г.
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791-801
Добавлено: 16 февраля 2024 г.
Малышев Д. С., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
Добавлено: 3 октября 2013 г.
Сироткин Д. В., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 4 P. 759-769
Добавлено: 20 ноября 2018 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Алексеев В. Е., Лозин В. В., Малышев Д. С. и др., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
В работе изучается вычислительная сложность нахождения наибольшего независимого множества вершин в планарных графах. В общем случае данная задача является NP-полной. Однако, при определенных ограничениях она становится полиномиально разрешимой. В работе выявляется графовый параметр, к изменению которого чувствительна сложность задачи и предлагаем несколько отрицательных (об NP-полноте) и положительных (о полиномиальной разрешимости) результатов, обобщающих несколько ранее известных ...
Добавлено: 7 ноября 2012 г.
Добавлено: 8 сентября 2021 г.
Малышев Д. С., Дискретная математика 2009 Т. 21 № 4 С. 129-134
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 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 ...
Добавлено: 30 октября 2013 г.