Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/156832
Full metadata record
DC FieldValueLanguage
dc.contributor.authorКотов, В. М.-
dc.contributor.authorОрлович, Ю. Л.-
dc.contributor.authorВолчкова, Г. П.-
dc.contributor.authorИржавский, П. А.-
dc.contributor.authorКартынник, Ю. А.-
dc.date.accessioned2016-09-28T12:13:55Z-
dc.date.available2016-09-28T12:13:55Z-
dc.date.issued2015-
dc.identifier.other№ гос. регистрации 20114354ru
dc.identifier.urihttp://elib.bsu.by/handle/123456789/156832-
dc.description.abstractОбъектом исследования являются задачи дискретной оптимизации и задачи теории графов. Цель работы состоит в разработке методов и алгоритмов дискретной математики для решения задач оптимизации, характеризации и распознавания, формулируемых в терминах теории графов, теории расписаний, разбиений и упаковки. Основные результаты исследований. Разработаны рекордные алгоритмы для семи онлайн версий задач теории расписаний с убывающими длительностями обслуживания и для онлайн версий задач упаковки с растяжением. Разработан асимптотически наилучший алгоритм для задачи теории расписаний Pm||Cmax с известной суммарной длительностью всех работ, основанный на использовании групповых технологий и вычислении динамической нижней оценки. Построены эффективные алгоритмы для решения задачи двумерного прямоугольного гильотинного раскроя полосы и прямоугольника. Для задачи теории расписаний Om||Cmax найдены новые свойства экстремальных плотных расписаний. Установлена вычислительная сложность и сложность аппроксимации и найдены полиномиально разрешимые случаи для ряда теоретико-графовых задач, связанных с понятиями независимости, доминирования и паросочетания в наследственных классах графов. Установлена co-NP-полнота задачи распознавания класса графов, в которых все максимальные индуцированные паросочетания имеют одинаковый размер, и найдена его характеризация в терминах минимальных запрещенных косогласованных подграфов. Получены новые достаточные условия полной циклической расширяемости графов и установлена вычислительная сложность задачи о гамильтоновом цикле в ряде классов графов с предписанными локальными ограничениями.ru
dc.language.isoruru
dc.publisherМинск : БГУru
dc.subjectЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математикаru
dc.titleМетоды и алгоритмы дискретной математики для решения задач оптимизации, характеризации и распознавания : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котовru
dc.typereportru
Appears in Collections:Отчеты 2015

Files in This Item:
File Description SizeFormat 
20114354-КОТОВ.doc5,77 MBMicrosoft WordView/Open
Show simple item record Google Scholar



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