1139 Методы решения задачи об оптимальной интервальной раскраске графа

Посыпкин Михаил Анатольевич

руководитель проекта

Старт

15.03.2022

Представление

29.04.2022

Постерная сессия

06.06.2022

Защита

03.11.2022

Паспорт проекта

Аннотация

Рассматривается следующая задача: имеется граф с размеченными вершинами – к каждой вершине приписано целое положительное число. Требуется приписать к каждой вершине целочисленный интервал, равный по длине приписанному числу так, чтобы левый конец интервала был неотрицательным, а интервалы, приписанные смежным вершинам, не пересекались. Цель – найти присваивание интервалов вершинам с минимальным максимумом правого конца. Данная сложная комбинаторная задача применяется при организации...

Отрасль

Информатика

Цель

Разработать и реализовать новые эффективные методы для указанной задачи. Интересны как точные методы, дающие оптимальное решения так и эвристики, например жадные алгоритмы, позволяющие получить некоторое приближение за разумное время.

Ожидаемые результаты

1. Новые алгоритмы решения задачи об интервальной раскраске графа.
2. Публикация по теме проекта.

Форма и способы промежуточного контроля

Защита проекта на проектной сессии.

Форма представления результатов

Отчет по проделанной работе

Ресурсное обеспечение

Не требуется

Имеющийся задел

Литература: 1. Krawczyk, H., & Kubale, M. (1985). An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Transactions on Computers, 34(09), 869-872. 2. Martin Charles Golumbic , Algorithmic Graph Theory and Perfect Graphs