?
Диаграммный подход в теории узлов и его приложения в теории графов
Вестник Московского университета. Серия 1: Математика. Механика. 2018. № 3. С. 65-71.
Никонов И. М., Ильютко Д. П.
Статья представляет собой обзор результатов одноименного цикла работ авторов, отмеченных премией имени И. И. Шувалова за научную деятельность I степени.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2010 № 4 С. 133-136
Изучаются минимальные по включению наследственные классы графов с NP-полной задачей о реберном списковом ранжировании, задаваемые небольшим количеством запрещенных порожденных подграфов. ...
Добавлено: 11 сентября 2012 г.
Лазарев А. А., М. : Московский физико-технический институт, 2008
Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения и быстродействия. Предлагается качественно новая схема нахождения приближённого решения. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным ...
Добавлено: 17 декабря 2012 г.
М. : ИПУ РАН, 2012
В сборнике представлены труды конференции с международным участием «ТЕХНИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА СИСТЕМ УПРАВЛЕНИЯ, КОНТРОЛЯ И ИЗМЕРЕНИЯ» УКИ`12 по следующим направлениям:
Научная тематика
1. Теория, методы исследования и проектирования, опыт применения технических средств (от датчиков до исполнительных механизмов), основанных на различных физических и схемотехнических принципах.
2. Теория, алгоритмы и программное обеспечение систем УКИ.
3. Анализ состояния, тенденций и перспектив ...
Добавлено: 29 декабря 2012 г.
М. : Изд-во механико-математического факультета МГУ, 2016
Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 20 по 25 июня 2016 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики. ...
Добавлено: 29 августа 2016 г.
Найдены условия существования и единственности решения проблемы минимизации функционала энергии системы векторных потенциалов ассоциированных с набором мер в комплексной плоскости. Полученные результаты являются самыми общими из известных на настоящий момент. ...
Добавлено: 13 декабря 2012 г.
Акчурин Р. М., Старичкова Ю. В., Шаграев А. Г., Вычислительные сети. Теория и практика 2009 № 2(15)
Структуры систем могут быть описаны различными способами, к основным из которых относятся: графический, списочный, матричный, графовый и теоретико-множественный. Для систем управления предприятием, имеющим множество связей с производством, с вышестоящими организациями, наиболее наглядным является графовое представление структуры. В данной работе проводится доказательство полноты набора операций по преобразованию структур, предложенных в работе. ...
Добавлено: 18 января 2013 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы и ее частные случаи. Приводятся результаты исследования известных нижних оценок. Выдвинута гипотеза о свойствах оптимального значения целевой функции в задаче с прерываниями и без прерываний обслуживания требований и представлено доказательство гипотезы для частных случаев задачи. Показано, что любой проект можно преобразовать в проект с "планарным" ...
Добавлено: 17 декабря 2012 г.
М. : МАКС Пресс, 2017
Сборник содержит доклады XVIII международной конференции «Проблемы теоретической кибернетики» (Пенза, 19–23 июня 2017 г.), организованной при поддержке Российского фонда фундаментальных исследований (проект No 17-01-20217-г). Тематика конференции включает следующие направления: синтез и сложность управляющих систем, надежность, контроль и диагностика управляющих систем, автоматы, языки и программирование, теория графов, комбинаторика, теория кодирования, теория распознавания образов, математическое про- граммирование ...
Добавлено: 25 августа 2017 г.
Задача разбиения графа заключается в разделении множества вершин графа на число непустых подмножеств так, чтобы общий вес ребер, соединяющих различные подмножества сводился к минимуму. Предшествующие исследования требуют ввода мощностей подмножеств или числа подмножеств для равнораспределения. В этой статье, проблема формулируется как Zero-one задача квадратичного программирования без ввода мощностей. Мы также представляем три формулировки равнозначного Zero-one ...
Добавлено: 31 декабря 2012 г.
Старичкова Ю. В., Незнанов А. А., Вестник Тамбовского университета. Серия: Естественные и технические науки 2012 Т. 17 № 2 С. 532-547
Рассматривается задача классификации семейств связных транзитивных графов степени 4 (ТГС4) на основе характеристик симметрии (строения группы автоморфизмов) и информации обо всех ТГС4 с числом вершин до 30. Предлагается один из вариантов классификации и конкретные бесконечные и конечные семейства, покрывающие все ТГС4 до 30 вершин, с возможностью расширения состава семейств с ростом числа вершин ТГС4. Построен ...
Добавлено: 11 сентября 2012 г.
Лазарев А. А., Садыков Р. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | rj | Lmax) и суммарного взвешенного числа запаздывающих требований (1 | rj | ΣwjUj). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. ...
Добавлено: 17 декабря 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2011 Т. 18 № 1 С. 70-76
Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Алексеев В. Е., Дискретный анализ и исследование операций 2008 Т. 15 № 1 С. 3-10
Доказывается полиномиальная разрешимость задачи о независимом множестве для бесконечного семейства подмножеств класса планарных графов. ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Субочев А. Н., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2008. No. 3.
Ключевой проблемой моделирования коллективного выбора является то, что победитель Кондорсе, т.е. альтернатива более предпочтительная для коллектива, чем любая другая альтернатива при парном сравнении, в общем случае отсутствует. Поэтому с конца 70-х гг. прошлого века предпринимались попытки локализовать результат выбора в некотором всегда непустом подмножестве множества альтернатив, на котором определено отношение мажоритарного доминирования, играющее роль системы ...
Добавлено: 26 декабря 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Малышев Д. С., Дискретная математика 2009 Т. 21 № 4 С. 129-134
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2009 Т. 16 № 1 С. 37-43
Доказывается, что для задачи о реберной 3-раскраске множество граничных классов бесконечно. ...
Добавлено: 31 августа 2012 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Шитов Я. Н., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Добавлено: 23 февраля 2016 г.
Екатеринбург : Издательство Уральского университета, 2012
Добавлено: 10 декабря 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.