Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/156832
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Котов, В. М. | - |
dc.contributor.author | Орлович, Ю. Л. | - |
dc.contributor.author | Волчкова, Г. П. | - |
dc.contributor.author | Иржавский, П. А. | - |
dc.contributor.author | Картынник, Ю. А. | - |
dc.date.accessioned | 2016-09-28T12:13:55Z | - |
dc.date.available | 2016-09-28T12:13:55Z | - |
dc.date.issued | 2015 | - |
dc.identifier.other | № гос. регистрации 20114354 | ru |
dc.identifier.uri | http://elib.bsu.by/handle/123456789/156832 | - |
dc.description.abstract | Объектом исследования являются задачи дискретной оптимизации и задачи теории графов. Цель работы состоит в разработке методов и алгоритмов дискретной математики для решения задач оптимизации, характеризации и распознавания, формулируемых в терминах теории графов, теории расписаний, разбиений и упаковки. Основные результаты исследований. Разработаны рекордные алгоритмы для семи онлайн версий задач теории расписаний с убывающими длительностями обслуживания и для онлайн версий задач упаковки с растяжением. Разработан асимптотически наилучший алгоритм для задачи теории расписаний Pm||Cmax с известной суммарной длительностью всех работ, основанный на использовании групповых технологий и вычислении динамической нижней оценки. Построены эффективные алгоритмы для решения задачи двумерного прямоугольного гильотинного раскроя полосы и прямоугольника. Для задачи теории расписаний Om||Cmax найдены новые свойства экстремальных плотных расписаний. Установлена вычислительная сложность и сложность аппроксимации и найдены полиномиально разрешимые случаи для ряда теоретико-графовых задач, связанных с понятиями независимости, доминирования и паросочетания в наследственных классах графов. Установлена co-NP-полнота задачи распознавания класса графов, в которых все максимальные индуцированные паросочетания имеют одинаковый размер, и найдена его характеризация в терминах минимальных запрещенных косогласованных подграфов. Получены новые достаточные условия полной циклической расширяемости графов и установлена вычислительная сложность задачи о гамильтоновом цикле в ряде классов графов с предписанными локальными ограничениями. | ru |
dc.language.iso | ru | ru |
dc.publisher | Минск : БГУ | ru |
dc.subject | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика | ru |
dc.title | Методы и алгоритмы дискретной математики для решения задач оптимизации, характеризации и распознавания : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов | ru |
dc.type | report | ru |
Appears in Collections: | Отчеты 2015 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
20114354-КОТОВ.doc | 5,77 MB | Microsoft Word | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.