?
Complexity classification of the edge coloring problem for a family of graph classes
Discrete Mathematics and Applications. 2017. Vol. 27. No. 2. P. 97-101.
Язык:
английский
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., 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 ...
Добавлено: 23 июня 2013 г.
Малышев Д. С., Пардалос П. О., Doklady Mathematics 2014 Vol. 89 No. 2 P. 253-256
Добавлено: 18 апреля 2014 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 4 P. 537-548
Добавлено: 21 января 2014 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 3 P. 412-419
...
Добавлено: 3 октября 2013 г.
Малышев Д. С., 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 г.
Малышев Д. С., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 345-354
The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or ...
Добавлено: 7 февраля 2013 г.
Малышев Д. С., Развенская О. О., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166
Добавлено: 21 ноября 2016 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.
Малышев Д. С., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
Добавлено: 3 октября 2013 г.
Малышев Д. С., Пардалос П. О., Optimization Letters 2015 Vol. 9 No. 5 P. 839-843
The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure
of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss ...
Добавлено: 26 сентября 2014 г.
Малышев Д. С., Грибанов Д. В., Discrete Optimization 2018 Vol. 29 P. 103-110
Добавлено: 8 апреля 2018 г.
Гафаров Е. Р., Долгий А., Лазарев А. А., / Elsevier. Series -- "Computers & Industrial Engineering". 2014.
In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...
Добавлено: 10 апреля 2015 г.
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 г.
Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
Добавлено: 18 декабря 2015 г.
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 г.
Малышев Д. С., 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 г.
Грибанов Д. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 227 P. 13-20
Добавлено: 23 апреля 2017 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Kazda A., Opršal J., Valeriote M. и др., Canadian Mathematical Bulletin 2020 P. 577-591
Добавлено: 15 июня 2020 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Сироткин Д. В., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 4 P. 759-769
Добавлено: 20 ноября 2018 г.