Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/158314
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Котов, В. М. | - |
dc.contributor.author | Орлович, Ю. Л. | - |
dc.contributor.author | Волчкова, Г. П. | - |
dc.contributor.author | Иржавский, П. А. | - |
dc.contributor.author | Картынник, Ю. А. | - |
dc.date.accessioned | 2016-10-12T11:45:31Z | - |
dc.date.available | 2016-10-12T11:45:31Z | - |
dc.date.issued | 2015 | - |
dc.identifier.other | № гос. регистрации 20120349 | ru |
dc.identifier.uri | http://elib.bsu.by/handle/123456789/158314 | - |
dc.description.abstract | Объектом исследования являются задачи теории расписаний и теории графов. Целью работы является исследование алгоритмической сложности и сложности аппроксимации теоретико-графовых задач, связанных с параметрами независимости и доминирования; построение эффективных алгоритмов для задач теории расписаний; исследование гамильтоновых свойств графов. Основные результаты исследований. Предложены модели, разработаны методы и приближенные алгоритмы для онлайн и семи онлайн версий задач теории расписаний с критерием минимизации общего времени завершения обслуживания всех работ. Получены новые оценки погрешности в задачах теории расписаний на основе детального изучения структуры множества оптимальных решений и использования динамических нижних оценок. Найдена характеризация класса хорошо согласованных графов в терминах минимальных запрещенных косогласованных подграфов. Установлена вычислительная сложность и сложность аппроксимации в конаследственных и окрестностно наследственных классах графов ряда теоретико-графовых параметров, родственных классическим числам независимости и доминирования. В предположении P NP для задач нахождения наименьшего доминирующего множества, наименьшего окрестностного множества, наименьшего максимального ирридантного множества доказано, что не существует полиномиального (k ln n)-приближенного алгоритма в классе расщепляемых доминантно-треугольных графов порядка n, где k >0 – некоторая фиксированная константа. Установлена вычислительная сложность задачи о гамильтоновом цикле в классе локально связных графов с дополнительными ограничениями на степени вершин. | ru |
dc.language.iso | ru | ru |
dc.publisher | Минск : БГУ | ru |
dc.subject | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика | ru |
dc.title | Модели, методы и алгоритмы для задач теории расписаний, разбиения, упаковки и теории графов : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов | ru |
dc.type | report | ru |
Располагается в коллекциях: | Отчеты 2015 |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
20120349-КОТОВ.doc | 2,92 MB | Microsoft Word | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.