?
Efficient Computation of Tolerances in the Weighted Independent Set Problem for Trees
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 lower tolerances related to this solution can be computed with O(n) time.
Язык:
английский
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58–64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.
Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Добавлено: 20 октября 2016 г.
Малышев Д. С., Пардалос П. О., Доклады Академии Наук. Информатика 2014 Т. 455 № 5 С. 529–532
Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве и двудольного графа с n вершинами и m рёбрами оптимальное решение вычисляется за время O(nm), а все допуски ...
Добавлено: 27 марта 2014 г.
Малышев Д. С., Пардалос П. О., Doklady Mathematics 2014 Vol. 89 No. 2 P. 253–256
Добавлено: 18 апреля 2014 г.
Малышев Д. С., Discrete Mathematics and Applications 2017 Vol. 27 No. 2 P. 97–101
Добавлено: 10 мая 2017 г.
Малышев Д. С., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81–96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Добавлено: 27 февраля 2017 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Доклады Академии Наук. Информатика 2013 Т. 450 № 4 С. 393–396
Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве на деревьях с n вершинами все верхние и нижние допуски вершин могут быть вычислены за время O(n). ...
Добавлено: 17 мая 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66–72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., 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 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 г.
Малышев Д. С., Дискретная математика 2013 Т. 25 № 2 С. 63–67
В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин. ...
Добавлено: 15 января 2014 г.
Алексеев В. Е., Замараев В. А., Захарова Д. В. и др., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 6(1) С. 165–172
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Добавлено: 3 февраля 2014 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26–44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Добавлено: 23 июня 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 1 С. 74–96
Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного ...
Добавлено: 11 сентября 2012 г.
Швыдун С. В., / NRU Higher School of Economics. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221–228
Добавлено: 23 июня 2013 г.
Малышев Д. С., Дискретная математика 2016 Т. 28 № 2 С. 44–50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Добавлено: 5 июля 2016 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104–130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 2 С. 75–87
Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества Free({P5,C5}). Доказано, что если для связного графа G задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого p она остается таковой в классе ...
Добавлено: 17 мая 2013 г.
Малышев Д. С., Optimization Letters 2014 Vol. 8 No. 8 P. 2261–2270
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...
Добавлено: 6 марта 2014 г.
Грибанов Д. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 227 P. 13–20
Добавлено: 23 апреля 2017 г.
Грибанов Д. В., Малышев Д. С., Мокеев Д. Б., Дискретный анализ и исследование операций 2020 Т. 27 № 3 С. 71–87
Рассматривается задача минимизации количества цветов в раскрасках вершин задаваемого графа так, что каждой вершине назначаются цвета, число которых равно задаваемому весу вершины, причём смежным вершинам назначаются различные цвета. Для всех наследственных классов, определяемых парой связных 5-вершинных порождённых запретов, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. В настоящей ...
Добавлено: 15 сентября 2020 г.
Сироткин Д. В., Малышев Д. С., Дискретный анализ и исследование операций 2018 Т. 25 № 4 С. 112–130
Задача о 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем 5 вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не ...
Добавлено: 28 ноября 2018 г.