Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/149665
Title: Комбинаторные модели и методы для решения задач теории расписаний и задач на графах и геометрических структурах : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов
Authors: Котов, В. М.
Орлович, Ю. Л.
Метельский, Ю. М.
Лепин, В. В.
Дугинов, О. И.
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: 2015
Publisher: Минск : БГУ
Abstract: Объектом исследования являются расписания и комбинаторно-геометриче-ские конфигурации (графы, гиперграфы, частично-выпуклые множества). Цель работы состоит в исследовании комбинаторных моделей и разработке методов решения ряда характеризационных, распознавательных и оптимизационных задач, связанных с расписаниями, графами и специальными объектами комбинаторно-геометрической природы. Основные результаты исследований. Предложен алгоритм, имеющий асимптотическую оценку 2, для классической задачи минимизации времени завершения проекта на многопроцессорной системе. Получена характеризация класса графов с ограниченной обобщенной краусовой размерностью при заданных дополнительных ограничениях. Разработаны эффективные полиномиальные алгоритмы решения проблемы распознавания частичной выпуклости объединения нескольких многогранных множеств. Найдены новые достаточные условия гамильтоновости графов и установлена сложность задачи распознавания гамильтоновости для ряда классов графов с предписанными локальными ограничениями. Разработаны алгоритмы для решения задачи о взвешенной независимой {K1, K2}-упаковке в классе деревьев с трудоемкостью O(n) и в классе унициклических графов с трудоемкостью O(n2), где n – число вершин в графе. Для задачи о бикликовом покрытии вершин графа построены полиномиальные приближенные алгоритмы с гарантированными оценками точности в виде частичных сумм гармонического ряда и доказана ее неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности, в предположении, что P ≠ NP, даже в случае, когда входной граф является сбалансированным двудольным.
URI: http://elib.bsu.by/handle/123456789/149665
Registration number: № гос. регистрации 20131164
Appears in Collections:Отчеты 2015

Files in This Item:
File Description SizeFormat 
Отчет 20131164-КОТОВ (1).doc8,03 MBMicrosoft WordView/Open


PlumX

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.