• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 38 публикаций
Сортировка:
по названию
по году
Статья
Malyshev D. Journal of Applied and Industrial Mathematics. 2010. Vol. 4. No. 2. P. 213-217.
Добавлено: 13 октября 2010
Статья
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.

Добавлено: 31 августа 2012
Статья
Вялый М. Н., Рубцов А. А. Дискретный анализ и исследование операций. 2012.

Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача регулярной реализуемости (проверки выполнимости некоторого регулярного свойства на заданном множестве слов) алгоритмически эквивалентна некоторой задаче о достижении автоматом принимающего состояния при чтении сверхслова.

Добавлено: 17 октября 2014
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2011. Т. 18. № 3. С. 83-87.

Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа ребер от числа вершин. Показано, что для любого натурального C в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]} эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]}  для любой неограниченной неубывающей функции f(n) : N → N, экспонента от которой растет быстрее, чем полином от n. Последний результат справедлив, если для задачи о независимом множестве нет субэкспоненциальных алгоритмов.

Добавлено: 11 сентября 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2012. Т. 19. № 1. С. 74-96.

Описаны все наследственные классы графов, определяемые не более чем тремя запрещенными порожденными подграфами (обструкциями), для которых задача о реберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным ("критическим") классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного типа, определяемые тремя и менее обструкциями, описаны.

Добавлено: 11 сентября 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2009. Т. 16. № 2. С. 85-94.

Рассматриваются класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями, и класс рёберных графов к графам этого класса. Известен ряд задач, для которых эти классы являются граничными. В работе исследуются общие свойства таких задач. Именно, доказывается достаточное условие граничности рассматриваемых классов. При помощи полученного инструмента к известным случаям граничности данных классов добавляется восемь новых.

Добавлено: 31 августа 2012
Статья
Малышев Д. С., Алексеев В. Е. Дискретный анализ и исследование операций. 2011. Т. 18. № 6. С. 61-70.

Найдены все граничные классы для задач о списковом ранжировании графов (в вершинном и реберном вариантах) относительно класса лесов. Это позволяет определить сложностной статус этих задач для любого наследственного класса, определяемого конечным множеством запрещенных подграфов относительно класса лесов.

Добавлено: 11 сентября 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2012. Т. 19. № 6. С. 37-48.

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту задачи о раскраске. Оказывается, что любой класс, граничный для задачи о реберной 3-раскраске, является граничным для задачи о хроматическом индексе. Вместе с тем, при любом k > 3 существует континуум классов графов, граничных для задачи о реберной k-раскраске, каждый из которых не является граничным для задачи о хроматическом числе. Формулируется необходимое условие существования граничных классов графов для задачи о вершинной 3-раскраске, не являющихся граничными для задачи о хроматическом числе. По мнению автора, заключение этого условия никогда не выполняется, поэтому таковых классов вовсе не существует.

Добавлено: 30 ноября 2012
Статья
Малышев Д. С., Мокеев Д. Б. Дискретный анализ и исследование операций. 2019. Т. 26. № 1. С. 74-88.

Описывается класс графов, у которых для каждого подграфа максимальное число вершинно непересекающихся 4-путей равно минимальной мощности множества вершин таких, что каждый 4-путь подграфа содержит хотя бы одну из этих вершин. Полностью описано множество минимальных запрещенных подграфов данного класса. Кроме того, представлено альтернативное описание класса, в основе которого лежит операция подразбиения ребер, применяемая к двудольным мультиграфам, и добавление так называемых висячих подграфов, изоморфных треугольникам и звездам. 

Добавлено: 4 марта 2019
Статья
Алексеев В. Е., Мокеев Д. Б. Дискретный анализ и исследование операций. 2012. Т. 19. № 4. С. 3-14.

Характеризуется класс графов, у которых для каждого порожденного подграфа максимальное число непересекающихся порожденных путей с тремя вершинами равно минимальному числу вершин, покрывающих все такие пути.

Добавлено: 7 декабря 2012
Статья
Малышев Д. С., Алексеев В. Е. Дискретный анализ и исследование операций. 2008. Т. 15. № 1. С. 3-10.

Доказывается полиномиальная разрешимость задачи о независимом множестве для бесконечного семейства подмножеств класса планарных графов.

Добавлено: 31 августа 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2013. Т. 20. № 3. С. 26-44.

Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов.

Добавлено: 23 июня 2013
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2009. Т. 16. № 5. С. 41-51.

Для задач о вершинной 3-раскраске и о реберной 3-раскраске указываются континуальные множества граничных классов графов. Это первые примеры задач на графах с множествами граничных классов такой мощности.

Добавлено: 31 августа 2012
Статья
Малышев Д. С., Алексеев В. Е. Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 3-11.

Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе.

Добавлено: 31 августа 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2013. Т. 20. № 6. С. 59-76.

Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность "критических" классов графов, включение которых в конечно определенный класс эквивалентно "труднорешаемости" задачи о реберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев "труднорешаемости" имеется всего 5 конечно определенных классов и 1 минорно замкнутый класс

Добавлено: 23 октября 2013
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2017. Т. 24. № 1. С. 81-96.

 Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До результатов настоящей работы имелся пример только одной задачи на графах, для которой в семействе сильно наследственных классов выявлены граничные классы. Более того, в семействе минорно замкнутых классов ни для одной задачи на графах не было известно ни одного граничного класса. В настоящей работе для обоих рассматриваемых семейств и нескольких классических задач на графах приводятся полные описания граничных классов. Для задачи 2-аддитивной аппроксимации ленточной ширины графа в семействе минорно замкнутых классов найден граничный класс, причём для двух других семейств критические классы для этой задачи не известны.

Добавлено: 27 февраля 2017
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2011. Т. 18. № 1. С. 70-76.

Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода.

Добавлено: 11 сентября 2012
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2011. Т. 18. № 1. С. 70-76.
Добавлено: 30 сентября 2011
Статья
Вялый М. Н., Леонтьев В., Осетров М. Дискретный анализ и исследование операций. 2002. Т. 9. № 4. С. 41-49.
Добавлено: 17 октября 2014
Статья
Малышев Д. С. Дискретный анализ и исследование операций. 2009. Т. 16. № 1. С. 37-43.

Доказывается, что для задачи о реберной 3-раскраске множество граничных классов бесконечно.

Добавлено: 31 августа 2012
Статья
Смирнова Н. В., Тарашнина С. И. Дискретный анализ и исследование операций. 2011. Т. 18. № 4. С. 77-93.
Добавлено: 28 сентября 2015
1 2