?
О факториальных подклассах класса графов без K_{1,3}
Дискретный анализ и исследование операций. 2013. Т. 20. № 6. С. 30-39.
Zamaraev V. A.
In press
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 if each of the following its subclasses is at most factorial: subclass of bipartite graphs, subclass of co-bipartite graphs, subclass of split graphs. In the paper we prove this conjecture for a subclasses of claw-free graphs, defined by two forbidden subgraphs.
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
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., 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
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
Malyshev D., Discrete Applied Mathematics 2016 Vol. 203 P. 117-126
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. ...
Added: October 9, 2015
Malyshev D., Журнал Средневолжского математического общества 2020 Т. 22 № 1 С. 38-47
Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске ...
Added: March 26, 2020
Malyshev D., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81-96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Added: February 27, 2017
Alekseev V., Zakharova D. V., Malyshev D. et al., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математика 2012 № 6(1) С. 115-120
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: May 17, 2013
Malyshev D., Дискретная математика 2012 Т. 24 № 4 С. 91-103
В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и NP-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот,
доказывается достаточное условие ...
Added: May 17, 2013
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2011 Т. 6 № 1 С. 169-173
Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах. ...
Added: June 28, 2012
Malyshev D., Razvenskaya O., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166
We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.
Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs. ...
Added: November 21, 2016
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2014 Т. 3 № 1 С. 288-290
В работе показывается, что задача о раскраске полиномиально разрешима в классе графов Free({claw,bull}). ...
Added: April 7, 2014
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
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 6(1) С. 165-172
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: February 3, 2014
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Added: November 30, 2012
Malyshev D., Pardalos P. M., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...
Added: December 18, 2015
Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423-432
We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...
Added: April 23, 2018
Malyshev D., Siberian Electronic Mathematical Reports 2014 Vol. 11 P. 811-822
We obtain a complete complexity dichotomy for the edge 3- colorability within the family of hereditary classes defined by forbidden
induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures. ...
Added: April 7, 2014
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2014 Vol. 8 No. 2 P. 245-255
The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem ...
Added: May 8, 2014
Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189
The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...
Added: January 28, 2020
Borzykh D., ЛЕНАНД, 2021
Книга представляет собой экспресс-курс по теории вероятностей в контексте начального курса эконометрики. В курсе в максимально доступной форме изложен тот минимум, который необходим для осознанного изучения начального курса эконометрики. Данная книга может не только помочь ликвидировать пробелы в знаниях по теории вероятностей, но и позволить в первом приближении выучить предмет «с нуля». При этом, благодаря доступности изложения и небольшому объему книги, ...
Added: February 20, 2021
В. Л. Попов, Математические заметки 2017 Т. 102 № 1 С. 72-80
Мы доказываем, что аффинно-треугольные подгруппы являются борелевскими подгруппами групп Кремоны. ...
Added: May 3, 2017
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Added: November 18, 2013
Min Namkung, Younghun K., Scientific Reports 2018 Vol. 8 No. 1 P. 16915-1-16915-18
Sequential state discrimination is a strategy for quantum state discrimination of a sender’s quantum
states when N receivers are separately located. In this report, we propose optical designs that can
perform sequential state discrimination of two coherent states. For this purpose, we consider not
only binary phase-shifting-key (BPSK) signals but also general coherent states, with arbitrary prior
probabilities. Since ...
Added: November 16, 2020