?
Оценка числа графов в наследственных классах с запрещенными графами маленького порядка
С. 173-175.
Zamaraev V. A.
In book
Н. Новгород : Нижегородский государственный университет им. Н.И. Лобачевского, 2011
Zamaraev V. A., В кн. : XVI Нижегородская сессия молодых ученых. Математические науки: Материалы докладов. Вып. 16.: Н. Новгород : Нижегородский государственный университет им. Н.И. Лобачевского, 2011. С. 26-27.
Описаны почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным графом. ...
Added: July 4, 2012
Alekseev V., Zamaraev V. A., Lozin V. V. et al., В кн. : XV Нижегородская сессия молодых ученых. Математические науки: Материалы докладов. Вып. 15.: Н. Новгород : Нижегородский государственный университет им. Н.И. Лобачевского, 2010. С. 16-17.
Описаны некоторые факториальные классы графов, определяемые двумя запрещенными графами. ...
Added: July 4, 2012
Zamaraev V. A., В кн. : Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.). : М. : Механико-математический факультет МГУ, 2010. С. 301-303.
Доказывается факториальность наследственных классов графов Free(K1,p+Op, Kp) при любом натуральном p > 1. ...
Added: July 4, 2012
Zamaraev V. A., В кн. : Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям. Ч. 1.: М. : Издательство МГУ, 2011. С. 29-33.
Доказывается факториальность некоторых семейств подклассов класса двудольных графов. ...
Added: July 4, 2012
Sirotkin D., Malyshev D., Дискретный анализ и исследование операций 2018 Т. 25 № 4 С. 112-130
Задача о 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем 5 вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не ...
Added: November 28, 2018
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2012 № 2 С. 149-151
Понятия минимального сложного и граничного классов графов являются полезными инструментами при анализе вычислительной сложности задач на графах. В данной статье доказывается, что для конечно определенных классов графов эти понятия совпадают. Приводится пример, показывающий, что для бесконечно определенных классов графов это не так. ...
Added: April 25, 2012
Zamaraev V. A., В кн. : Доклады Одесского семинара по дискретной математике. Вып. 12.: Одесса : Одесский национальный университет имени И.И. Мечникова, 2011. С. 28-31.
Описаны все наследственные подклассы класса хордальных двудольных графов с органиченной древесной шириной. ...
Added: July 4, 2012
Lozin V. V., Mayhil C., Zamaraev V. A., European Journal of Combinatorics 2012 Vol. 33 No. 4 P. 534-543
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Lozin V. V., Mayhil C., Zamaraev V. A., Electronic Journal of Combinatorics 2011 Vol. 18 No. 1 P. 1-14
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2011 Т. 6 № 1 С. 169-173
Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах. ...
Added: June 28, 2012
Lozin V. V., Dabrowski K., Zamaraev V. A., Discrete Mathematics 2012 Vol. 312 No. 16 P. 2457-2465
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e., closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59-76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Added: October 23, 2013
Zamaraev V. A., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 30-39
For a set of labeled graphs X, let Xn be the set of n-vertex graphs from X. Hereditary class X is called at most factorial if there exist positive constants c,n0 such that |Xn| < n^{cn} for all n > n0. Lozin's conjecture states that hereditary class X is at most factorial if and only ...
Added: November 18, 2013
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 3(1) С. 181-187
Понятие относительного граничного класса является полезным при анализе вычислительной сложности задач на графах в семействе наследственных классов графов. В настоящей работе рассматривается факторизация решетки наследственных классов графов по отношению равенства относительных граничных систем и выявляется ряд ее свойств. ...
Added: October 3, 2013
Razvenskaya O., Malyshev D., Дискретный анализ и исследование операций 2021 Т. 28 № 1 С. 15-47
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно ее весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порожденными запретами, кроме четырех случаев, известна вычислительная сложность ...
Added: December 15, 2020
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
Zamaraev V. A., Moscow Journal of Combinatorics and Number Theory 2011 Vol. 1 No. 3 P. 277-286
For a graph property X, let Xn be the set of graphs with the vertex set {1, . . . , n} that satisfy the property X. A property X is called factorial if X is hereditary (i. e. closed under taking induced subgraphs) and nc1n ≤ X ≤ nc2n for some positive constants c1 ...
Added: June 28, 2012