?
Классы планарных графов с полиномиально разрешимой задачей о независимом множестве
Дискретный анализ и исследование операций. 2008. Т. 15. № 1. С. 3-10.
Malyshev D., Alekseev V.
Research target:
Mathematics
Language:
Russian
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
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 Т. 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., Дискретный анализ и исследование операций 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., Sirotkin D., Дискретный анализ и исследование операций 2017 Т. 24 № 3 С. 35-60
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. В данной работе доказываем полиномиальную разрешимость этой задачи для субкубических планарных графов, не содержащих порождённого дерева, получаемого отождествлением концов трёх путей длины 3, 3 и 2 соответственно. ...
Added: August 31, 2017
Malyshev D., Дискретная математика 2013 Т. 25 № 2 С. 63-67
В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин. ...
Added: January 15, 2014
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 1 С. 74-96
Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26-44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Added: June 23, 2013
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2007 № 2 С. 165-168
The Independent Set Problem for planar graphs is known to be NP-complete. In this paper, its polynomial solvability for some subclasses of planar graphs is proved. ...
Added: November 25, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 2 С. 75-87
Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества Free({P5,C5}). Доказано, что если для связного графа G задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого p она остается таковой в классе ...
Added: May 17, 2013
Malyshev D., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81-96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Added: February 27, 2017
Malyshev D., Alekseev V., Дискретный анализ и исследование операций 2008 Т. 15 № 6 С. 3-11
Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач ...
Added: August 31, 2012
Malyshev D., Дискретный анализ и исследование операций 2009 Т. 16 № 6 С. 43-51
Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов. ...
Added: August 31, 2012
Zamaraev V. A., Malyshev D., Mokeev D. B., Вестник Нижегородского университета им. Н.И. Лобачевского 2010 Т. 6 С. 143-147
Известно, что задача о доминирующем множестве в классе расщепляемых графов NP-полна. Изучается влияние степеней некоторых вершин таких графов на вычислительную сложность этой задачи. ...
Added: June 28, 2012
Malyshev D., Pardalos P. M., Доклады Академии Наук. Информатика 2014 Т. 455 № 5 С. 529-532
Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве и двудольного графа с n вершинами и m рёбрами оптимальное решение вычисляется за время O(nm), а все допуски ...
Added: March 27, 2014
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
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017
Malyshev D., Дискретная математика 2016 Т. 28 № 2 С. 44-50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Added: July 5, 2016
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
Старичкова Ю. В., Neznanov A., Вестник Тамбовского университета. Серия: Естественные и технические науки 2012 Т. 17 № 2 С. 532-547
Рассматривается задача классификации семейств связных транзитивных графов степени 4 (ТГС4) на основе характеристик симметрии (строения группы автоморфизмов) и информации обо всех ТГС4 с числом вершин до 30. Предлагается один из вариантов классификации и конкретные бесконечные и конечные семейства, покрывающие все ТГС4 до 30 вершин, с возможностью расширения состава семейств с ростом числа вершин ТГС4. Построен ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2011 Т. 18 № 1 С. 70-76
Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода. ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2009 Т. 16 № 1 С. 37-43
Доказывается, что для задачи о реберной 3-раскраске множество граничных классов бесконечно. ...
Added: August 31, 2012
М. : Изд-во механико-математического факультета МГУ, 2016
Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 20 по 25 июня 2016 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики. ...
Added: August 29, 2016
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Added: November 30, 2012