?
Оценка числа графов в некоторых подклассах двудольных графов
С. 29–33.
Замараев В. А.
Доказывается факториальность некоторых семейств подклассов класса двудольных графов.
В книге
Ч. 1. , М.: Издательство МГУ, 2011.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Добавлено: 3 декабря 2024 г.
Развенская О. О., Малышев Д. С., Дискретный анализ и исследование операций 2021 Т. 28 № 1 С. 15–47
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно ее весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порожденными запретами, кроме четырех случаев, известна вычислительная сложность ...
Добавлено: 15 декабря 2020 г.
Сироткин Д. В., Малышев Д. С., Дискретный анализ и исследование операций 2018 Т. 25 № 4 С. 112–130
Задача о 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем 5 вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не ...
Добавлено: 28 ноября 2018 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 2019.
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59–76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Добавлено: 23 октября 2013 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 3(1) С. 181–187
Понятие относительного граничного класса является полезным при анализе вычислительной сложности задач на графах в семействе наследственных классов графов. В настоящей работе рассматривается факторизация решетки наследственных классов графов по отношению равенства относительных граничных систем и выявляется ряд ее свойств. ...
Добавлено: 3 октября 2013 г.
Чернобай В. Б., Автоматизация и современные технологии 2009 № 8 С. 17–19
Рассмотрен двудольный граф и определено его совершенное или максимальное частичное паросочетание для использования свободного сетевого машинного времени. ...
Добавлено: 10 апреля 2013 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545–3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Замараев В. А., В кн.: Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.).: М.: Механико-математический факультет МГУ, 2010. С. 301–303.
Доказывается факториальность наследственных классов графов Free(K1,p+Op, Kp) при любом натуральном p > 1. ...
Добавлено: 4 июля 2012 г.
Алексеев В. Е., Замараев В. А., Лозин В. В. и др., В кн.: XV Нижегородская сессия молодых ученых. Математические науки: Материалы докладовВып. 15.: Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2010. С. 16–17.
Описаны некоторые факториальные классы графов, определяемые двумя запрещенными графами. ...
Добавлено: 4 июля 2012 г.
Замараев В. А., В кн.: XVI Нижегородская сессия молодых ученых. Математические науки: Материалы докладовВып. 16.: Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2011. С. 26–27.
Описаны почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным графом. ...
Добавлено: 4 июля 2012 г.
Замараев В. А., В кн.: Доклады Одесского семинара по дискретной математикеВып. 12.: Одесса: Одесский национальный университет имени И.И. Мечникова, 2011. С. 28–31.
Описаны все наследственные подклассы класса хордальных двудольных графов с органиченной древесной шириной. ...
Добавлено: 4 июля 2012 г.
Замараев В. А., В кн.: Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.).: Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2011. С. 173–175.
Описываются все факториальные классы, у которых множество запрещенных подграфов состоит из графов с не более чем четырьмя вершинами. ...
Добавлено: 2 июля 2012 г.
Лозин В. В., Дабровски К., Замараев В. А., Discrete Mathematics 2012 Vol. 312 No. 16 P. 2457–2465
Для класса графов X через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями ...
Добавлено: 28 июня 2012 г.