?
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.
Под общей редакцией: F. Fomin, Подольский В. В.
Козачинский А. Н., , 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. 232-243.
Добавлено: 24 мая 2018 г.
Рубцов А. А., Вялый М. Н., , 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 г.
Гурвич В. А., , 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. 1-14.
Добавлено: 10 октября 2018 г.
Ключевые слова: Computational Complexity
Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
Добавлено: 18 декабря 2015 г.
Шитов Я. Н., SIAM Journal on Optimization 2017 Vol. 27 No. 3 P. 1898-1909
Добавлено: 24 октября 2017 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Яновский Е. А., Ong L., Artificial Intelligence 2018 No. 261 P. 1-15
Добавлено: 25 февраля 2019 г.
Kazda A., Opršal J., Valeriote M. и др., Canadian Mathematical Bulletin 2020 P. 577-591
Добавлено: 15 июня 2020 г.
Малышев Д. С., / 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 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2012 Vol. 6 No. 1 P. 97-99
Добавлено: 7 декабря 2012 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443
Добавлено: 24 сентября 2020 г.
Kontchakov R., Pratt-Hartmann I., Nenov Y. и др., ACM Transactions on Computational Logic 2013 Vol. 14 No. 2 P. 13.1-13.48
We consider the quantifier-free languages, Bc and Bc°, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of Rn (n ≥ 2) and, additionally, over the regular closed semilinear sets of Rn. ...
Добавлено: 25 марта 2015 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 3 P. 412-419
...
Добавлено: 3 октября 2013 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Малышев Д. С., 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 г.
Малышев Д. С., 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 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Алексеев В. Е., Лозин В. В., Малышев Д. С. и др., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
В работе изучается вычислительная сложность нахождения наибольшего независимого множества вершин в планарных графах. В общем случае данная задача является NP-полной. Однако, при определенных ограничениях она становится полиномиально разрешимой. В работе выявляется графовый параметр, к изменению которого чувствительна сложность задачи и предлагаем несколько отрицательных (об NP-полноте) и положительных (о полиномиальной разрешимости) результатов, обобщающих несколько ранее известных ...
Добавлено: 7 ноября 2012 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
Задача о вершинной 3-раекраеке для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NР-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. ...
Добавлено: 2 июля 2018 г.
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 г.
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 г.
Artale A., Kontchakov R., Ryzhikov V. и др., ACM Transactions on Computational Logic 2014 Vol. 15 No. 3 P. 25.1-25.50
We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted over the ...
Добавлено: 25 марта 2015 г.
Малышев Д. С., 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. ...
Добавлено: 7 апреля 2014 г.