Logo BSU

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

Files in This Item:
File Description SizeFormat 
20114354-КОТОВ.doc5,77 MBMicrosoft WordView/Open


PlumX

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