Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
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).doc | 8,03 MB | Microsoft Word | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.