?
Некоторые факториальные классы графов, определяемые двумя запрещенными графами
С. 16–17.
Алексеев В. Е., Замараев В. А., Лозин В. В., Мэйхил К.
Описаны некоторые факториальные классы графов, определяемые двумя запрещенными графами.
Язык:
русский
В книге
Вып. 15. , Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2010.
Дахно Г. С., Малышев Д. С., Математические заметки 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 г.
Замараев В. А., В кн.: XVI Нижегородская сессия молодых ученых. Математические науки: Материалы докладовВып. 16.: Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2011. С. 26–27.
Описаны почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным графом. ...
Добавлено: 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 г.