?
Факториальные подклассы квазиреберных графов, определяемые одним запрещенным подграфом
С. 26–27.
Замараев В. А.
Описаны почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным графом.
Язык:
русский
В книге
Вып. 16. , Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 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 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59–76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Добавлено: 23 октября 2013 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 3(1) С. 181–187
Понятие относительного граничного класса является полезным при анализе вычислительной сложности задач на графах в семействе наследственных классов графов. В настоящей работе рассматривается факторизация решетки наследственных классов графов по отношению равенства относительных граничных систем и выявляется ряд ее свойств. ...
Добавлено: 3 октября 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 г.
Замараев В. А., В кн.: Доклады Одесского семинара по дискретной математикеВып. 12.: Одесса: Одесский национальный университет имени И.И. Мечникова, 2011. С. 28–31.
Описаны все наследственные подклассы класса хордальных двудольных графов с органиченной древесной шириной. ...
Добавлено: 4 июля 2012 г.
Замараев В. А., В кн.: Материалы VIII Молодежной научной школы по дискретной математике и ее приложениямЧ. 1.: М.: Издательство МГУ, 2011. С. 29–33.
Доказывается факториальность некоторых семейств подклассов класса двудольных графов. ...
Добавлено: 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 г.
Алексеев В. Е., Замараев В. А., Захарова Д. В. и др., Вестник Нижегородского университета им. Н.И. Лобачевского 2011 Т. 6 № 1 С. 169–173
Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах. ...
Добавлено: 28 июня 2012 г.
Лозин В. В., Мэйхил К., Замараев В. А., Electronic Journal of Combinatorics 2011 Vol. 18 No. 1 P. 1–14
Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями ...
Добавлено: 28 июня 2012 г.
Замараев В. А., Moscow Journal of Combinatorics and Number Theory 2011 Vol. 1 No. 3 P. 277–286
Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ X ≤ nc2n для некоторых положительных констант c1 и c2. Граф G называется квазиреберным, если ...
Добавлено: 28 июня 2012 г.
Лозин В. В., Мэйхил К., Замараев В. А., European Journal of Combinatorics 2012 Vol. 33 No. 4 P. 534–543
Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями ...
Добавлено: 28 июня 2012 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2012 № 2 С. 149–151
Понятия минимального сложного и граничного классов графов являются полезными инструментами при анализе вычислительной сложности задач на графах. В данной статье доказывается, что для конечно определенных классов графов эти понятия совпадают. Приводится пример, показывающий, что для бесконечно определенных классов графов это не так. ...
Добавлено: 25 апреля 2012 г.