Logo BSU

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/149665
Заглавие документа: Комбинаторные модели и методы для решения задач теории расписаний и задач на графах и геометрических структурах : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов
Авторы: Котов, В. М.
Орлович, Ю. Л.
Метельский, Ю. М.
Лепин, В. В.
Дугинов, О. И.
Тема: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Дата публикации: 2015
Издатель: Минск : БГУ
Аннотация: Объектом исследования являются расписания и комбинаторно-геометриче-ские конфигурации (графы, гиперграфы, частично-выпуклые множества). Цель работы состоит в исследовании комбинаторных моделей и разработке методов решения ряда характеризационных, распознавательных и оптимизационных задач, связанных с расписаниями, графами и специальными объектами комбинаторно-геометрической природы. Основные результаты исследований. Предложен алгоритм, имеющий асимптотическую оценку 2, для классической задачи минимизации времени завершения проекта на многопроцессорной системе. Получена характеризация класса графов с ограниченной обобщенной краусовой размерностью при заданных дополнительных ограничениях. Разработаны эффективные полиномиальные алгоритмы решения проблемы распознавания частичной выпуклости объединения нескольких многогранных множеств. Найдены новые достаточные условия гамильтоновости графов и установлена сложность задачи распознавания гамильтоновости для ряда классов графов с предписанными локальными ограничениями. Разработаны алгоритмы для решения задачи о взвешенной независимой {K1, K2}-упаковке в классе деревьев с трудоемкостью O(n) и в классе унициклических графов с трудоемкостью O(n2), где n – число вершин в графе. Для задачи о бикликовом покрытии вершин графа построены полиномиальные приближенные алгоритмы с гарантированными оценками точности в виде частичных сумм гармонического ряда и доказана ее неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности, в предположении, что P ≠ NP, даже в случае, когда входной граф является сбалансированным двудольным.
URI документа: http://elib.bsu.by/handle/123456789/149665
Регистрационный номер: № гос. регистрации 20131164
Располагается в коллекциях:Отчеты 2015

Полный текст документа:
Файл Описание РазмерФормат 
Отчет 20131164-КОТОВ (1).doc8,03 MBMicrosoft WordОткрыть
Показать полное описание документа Статистика Google Scholar



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.