Logo BSU

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

Files in This Item:
File Description SizeFormat 
20120349-КОТОВ.doc2,92 MBMicrosoft WordView/Open


PlumX

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