?
Vertex coloring of graphs with few obstructions
Discrete Applied Mathematics. 2017. Vol. 216. P. 273-280.
Лозин В. В., Малышев Д. С.
We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.
Язык:
английский
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Малышев Д. С., Optimization Letters 2014 Vol. 8 No. 8 P. 2261-2270
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...
Добавлено: 6 марта 2014 г.
Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833-845
Добавлено: 18 сентября 2014 г.
Малышев Д. С., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
Добавлено: 3 октября 2013 г.
Малышев Д. С., Развенская О. О., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166
Добавлено: 21 ноября 2016 г.
Лебедева А. В., Фундаментальная и прикладная математика 2014 Т. 19 № 2 С. 125-149
Рассматривается экстремальная задача о раскрасках гиперграфов. Пусть k — натуральное число. Требуется найти величину m(k,n), равную минимальному количеству рёбер n-однородного гиперграфа, не допускающего таких двухцветных раскрасок множества вершин, что в каждом ребре гиперграфа содержатся по крайней мере k вершин каждого цвета. В работе получены верхние оценки величин m(k,n) для малых значений k, n, найдено значение ...
Добавлено: 19 июля 2015 г.
Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 32 No. 1 P. 226-243
Добавлено: 4 апреля 2015 г.
Малышев Д. С., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. © 2015 Elsevier B.V. All rights reserved. ...
Добавлено: 7 апреля 2014 г.
Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
Добавлено: 18 декабря 2015 г.
Добавлено: 28 августа 2017 г.
Гринес В. З., Малышев Д. С., Починка О. В. и др., Regular and Chaotic Dynamics 2016 Vol. 21 No. 2 P. 189-203
Добавлено: 5 апреля 2016 г.
Малышев Д. С., Грибанов Д. В., Discrete Optimization 2018 Vol. 29 P. 103-110
Добавлено: 8 апреля 2018 г.
Пенза : ПГУ, 2015
В сборник трудов включены доклады юбилейного ХХ-го Международного симпозиума «Надежность и качество», проходившего с 25 по 31 мая 2015 г. в городе Пензе.
Рассмотрены актуальные проблемы теории и практики повышения надежности и качества; эффективности внедрения инновационных и информационных технологий в фундаментальных научных и прикладных исследованиях, образовательных и коммуникативных системах и средах, экономике и юриспруденции; методов и ...
Добавлено: 31 мая 2015 г.
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Добавлено: 13 февраля 2013 г.
Кузнецов В. О., Логистика и управление цепями поставок 2018 № 4 (87) С. 27-33
Одним из вариантов более гибкого подхода к анализу надежности цепей поставок нам представляется метод главных компонент (PCA). Учитывая большое количество переменных, описывающих цепь поставок, является сложной задачей - проанализировать в двумерном пространстве структуру переменных. Метод PCA позволяет перейти, в рамках анализа зависимостей переменных, от многомерного пространства к маломерному, оставляя для анализа саму полезную информацию, находящуюся ...
Добавлено: 29 ноября 2018 г.
Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40-58
Добавлено: 11 марта 2018 г.
Акопов А. С., Beklaryan L. A., Saghatelyan A. K., Environmental Modelling and Software 2019 Vol. 116 P. 7-25
Добавлено: 24 февраля 2019 г.
Марширов В. В., Марширова Л. Е., Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111-120
Рассматривается задача определения скорости охлаждения металла в процессе затвердевания при пересечениии температуры ликвидуса при интенсивном теплоотводе с его поверхности. Решение данной задачи необходимо для определения технологических режимов, граничных и начальных условий при которых могут буть получены новые сплавы с микрокристаллическими структурами. Приведены необходимые конечно-разностные уравнения, описан алгоритм, с использованием известных экспериментальных данных проведено тестирование созданной ...
Добавлено: 17 ноября 2013 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.