?
О минимальных сложных классах графов
Дискретный анализ и исследование операций. 2009. Т. 16. № 6. С. 43-51.
Research target:
Mathematics
Language:
Russian
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 1 С. 74-96
Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного ...
Added: September 11, 2012
Malyshev D., Alekseev V., Дискретный анализ и исследование операций 2011 Т. 18 № 6 С. 61-70
Найдены все граничные классы для задач о списковом ранжировании графов (в вершинном и реберном вариантах) относительно класса лесов. Это позволяет определить сложностной статус этих задач для любого наследственного класса, определяемого конечным множеством запрещенных подграфов относительно класса лесов. ...
Added: September 11, 2012
Malyshev D., Alekseev V., Дискретный анализ и исследование операций 2008 Т. 15 № 6 С. 3-11
Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач ...
Added: August 31, 2012
Malyshev D., Дискретный анализ и исследование операций 2009 Т. 16 № 2 С. 85-94
Рассматриваются класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями, и класс рёберных графов к графам этого класса. Известен ряд задач, для которых эти классы являются граничными. В работе исследуются общие свойства таких задач. Именно, доказывается достаточное условие граничности рассматриваемых классов. При помощи полученного инструмента к известным случаям ...
Added: August 31, 2012
Malyshev D., Дискретный анализ и исследование операций 2011 Т. 18 № 1 С. 70-76
Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода. ...
Added: September 11, 2012
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Added: August 31, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59-76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Added: October 23, 2013
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26-44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Added: June 23, 2013
Malyshev D., Дискретный анализ и исследование операций 2011 Т. 18 № 3 С. 83-87
Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа ребер от числа вершин. Показано, что для любого натурального C в классе графов ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]} эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Added: August 31, 2012
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2012 № 2 С. 149-151
Понятия минимального сложного и граничного классов графов являются полезными инструментами при анализе вычислительной сложности задач на графах. В данной статье доказывается, что для конечно определенных классов графов эти понятия совпадают. Приводится пример, показывающий, что для бесконечно определенных классов графов это не так. ...
Added: April 25, 2012
Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...
Added: September 11, 2012
Alekseev V., Zakharova D. V., Malyshev D. et al., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математика 2012 № 6(1) С. 115-120
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: May 17, 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
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Added: November 30, 2012
Malyshev D., Дискретный анализ и исследование операций 2009 Т. 16 № 1 С. 37-43
Доказывается, что для задачи о реберной 3-раскраске множество граничных классов бесконечно. ...
Added: August 31, 2012
Zamaraev V. A., Malyshev D., Mokeev D. B., Вестник Нижегородского университета им. Н.И. Лобачевского 2010 Т. 6 С. 143-147
Известно, что задача о доминирующем множестве в классе расщепляемых графов NP-полна. Изучается влияние степеней некоторых вершин таких графов на вычислительную сложность этой задачи. ...
Added: June 28, 2012
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., Дискретная математика 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
Malyshev D., Alekseev V., Journal of Applied and Industrial Mathematics 2008 Vol. 3 No. 1 P. 1-5
The polynomial solvability of the independent set problem is proved for an infinite family of subsets of the class of planar graphs. ...
Added: August 31, 2012
Shitov Y., 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. ...
Added: February 23, 2016
М. : Изд-во механико-математического факультета МГУ, 2016
Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 20 по 25 июня 2016 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики. ...
Added: August 29, 2016
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017