?
О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами
Дискретный анализ и исследование операций. 2022. Т. 29. № 2. С. 38-61.
Malyshev D., Дугинов О. И.
Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Added: October 20, 2016
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26-44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Added: June 23, 2013
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...
Added: June 6, 2012
Kokhov V. A., Ткаченко С. В., Программные продукты и системы 2010 № 4 С. 22-22
The article describes the original software tools for an experimental estimation of computational complexity of software solutions for problems on graph models of systems. The classes of the solved problems and the tools for analysis of results are listed. The method based on selection of graph models by their structural complexity is introduced. ...
Added: October 14, 2012
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017
Malyshev D., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81-96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Added: February 27, 2017
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...
Added: June 23, 2013
Goldengorin B. I., Malyshev D., Pardalos P. M., 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 ...
Added: June 23, 2013
Malyshev D., Дискретная математика 2013 Т. 25 № 2 С. 63-67
В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин. ...
Added: January 15, 2014
Sirotkin D., Malyshev D., Дискретный анализ и исследование операций 2018 Т. 25 № 4 С. 112-130
Задача о 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем 5 вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не ...
Added: November 28, 2018
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 1 С. 74-96
Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59-76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Added: October 23, 2013
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 6(1) С. 165-172
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: February 3, 2014
Gribanov D., Malyshev D., Mokeev D. B., Дискретный анализ и исследование операций 2020 Т. 27 № 3 С. 71-87
Рассматривается задача минимизации количества цветов в раскрасках вершин задаваемого графа так, что каждой вершине назначаются цвета, число которых равно задаваемому весу вершины, причём смежным вершинам назначаются различные цвета. Для всех наследственных классов, определяемых парой связных 5-вершинных порождённых запретов, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. В настоящей ...
Added: September 15, 2020
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Added: August 31, 2012
Malyshev D., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Added: December 25, 2020
Malyshev D., Дискретная математика 2016 Т. 28 № 2 С. 44-50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Added: July 5, 2016
Shvydun S., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...
Added: October 20, 2015
Koldanov A. P., Koldanov P., Semenov D., Журнал Новой экономической ассоциации 2021 Т. 2 № 50 С. 12-34
. The problem of analysis of pairwise connections between stocks of financial market by observations on stock returns is considered. Such problem arise in stock market network analysis. It is assumed that joint distribution of stock returns belongs to the wide class of elliptical distributions. Classical Pearson correlation, Fechner correlation and Kendall correlation are used ...
Added: June 17, 2021
Yasnitsky L., Ваулева С. В., Сафонова Д. Н. et al., Всероссийский криминологический журнал 2015 Т. 9 № 3 С. 423-430
Modern criminalists do not share a common opinion regarding the choice of parameters which could be used to work out a system of characteristics to differentiate a maniac killer from an ordinary person. This hinders the development of efficient software for investigation purposes. The paper describes the experience of developing a neural network that can ...
Added: October 1, 2015
Springer, 2021
This book constitutes the proceedings of the 16th International Conference on Formal Concept Analysis, ICFCA 2021, held in Strasbourg, France, in June/July 2021.
The 14 full papers and 5 short papers presented in this volume were carefully reviewed and selected from 32 submissions. The book also contains four invited contributions in full paper length.
The research part ...
Added: July 10, 2021
Пермь : Пермский государственный национальный исследовательский университет, 2020
В сборнике представлены статьи участников Всероссийской научно-практической конференции молодых ученых с международным участием «Математика и междисциплинарные исследования – 2020». На конференцию было прислано более ста статей из различных регионов России, а также из ближнего
и дальнего зарубежья. По итогам работы экспертной комиссии для публикации было отобрано шестьдесят две статьи. Каждая статья оценивалась группой экспертов в той области, которая рассматривается автором.
Представленные ...
Added: December 10, 2020
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...
Added: January 30, 2021
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Added: February 13, 2013