?
Критерий граничности и его применения
Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 3-11.
Малышев Д. С., Алексеев В. Е.
Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе.
Научное направление:
Математика
Язык:
русский
Малышев Д. С., Дискретный анализ и исследование операций 2009 Т. 16 № 2 С. 85-94
Рассматриваются класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями, и класс рёберных графов к графам этого класса. Известен ряд задач, для которых эти классы являются граничными. В работе исследуются общие свойства таких задач. Именно, доказывается достаточное условие граничности рассматриваемых классов. При помощи полученного инструмента к известным случаям ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2009 Т. 16 № 6 С. 43-51
Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов. ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Алексеев В. Е., Дискретный анализ и исследование операций 2011 Т. 18 № 6 С. 61-70
Найдены все граничные классы для задач о списковом ранжировании графов (в вершинном и реберном вариантах) относительно класса лесов. Это позволяет определить сложностной статус этих задач для любого наследственного класса, определяемого конечным множеством запрещенных подграфов относительно класса лесов. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 1 С. 74-96
Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26-44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Добавлено: 23 июня 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2011 Т. 18 № 1 С. 70-76
Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2011 Т. 18 № 3 С. 83-87
Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа ребер от числа вершин. Показано, что для любого натурального C в классе графов ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]} эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2009 Т. 16 № 1 С. 37-43
Доказывается, что для задачи о реберной 3-раскраске множество граничных классов бесконечно. ...
Добавлено: 31 августа 2012 г.
Замараев В. А., Малышев Д. С., Мокеев Д. Б., Вестник Нижегородского университета им. Н.И. Лобачевского 2010 Т. 6 С. 143-147
Известно, что задача о доминирующем множестве в классе расщепляемых графов NP-полна. Изучается влияние степеней некоторых вершин таких графов на вычислительную сложность этой задачи. ...
Добавлено: 28 июня 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59-76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Добавлено: 23 октября 2013 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., 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 г.
Малышев Д. С., Дискретная математика 2016 Т. 28 № 2 С. 44-50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Добавлено: 5 июля 2016 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
М. : Изд-во механико-математического факультета МГУ, 2016
Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 20 по 25 июня 2016 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики. ...
Добавлено: 29 августа 2016 г.
Сироткин Д. В., Малышев Д. С., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Добавлено: 7 сентября 2017 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 3(1) С. 181-187
Понятие относительного граничного класса является полезным при анализе вычислительной сложности задач на графах в семействе наследственных классов графов. В настоящей работе рассматривается факторизация решетки наследственных классов графов по отношению равенства относительных граничных систем и выявляется ряд ее свойств. ...
Добавлено: 3 октября 2013 г.
Шитов Я. Н., 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 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2010 № 4 С. 133-136
Изучаются минимальные по включению наследственные классы графов с NP-полной задачей о реберном списковом ранжировании, задаваемые небольшим количеством запрещенных порожденных подграфов. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.