Статья

Название статьи ВЗАИМОДЕЙСТВИЕ В ПОСЛЕДОВАТЕЛЬНЫЕ ПРОМЕЖУТКИ ВРЕМЕНИ
Автор Т.А. Магомедов
Рубрика РАЗДЕЛ VII. КРАТКИЕ СООБЩЕНИЯ
Месяц, год 06, 2012
Индекс УДК 519.682
DOI
Аннотация Целью данной работы является анализ реберной интервальной раскраски двудольного бирегулярного графа. В статье рассмотрено взаимодействие объектов в последовательные промежутки времени в соответствии с предписанными операциями. Взаимодействия между объектами, принадлежащими одной доли, исключены. Задача составления расписания формулируется как задача правильной реберной раскраски графа. Построен эффективный полиномиальный алгоритм, распознающий реберную интервальную раскраску двудольного бирегулярного графа. Актуальными являются поиск частных случаев, когда задачи разрешимы за полиномиальное время, и построение эффективных алгоритмов приближенного решения.

Скачать в PDF

Ключевые слова Расписание; двудольный граф; правильная раскраска; интервальная раскраска; NP-полнота.
Библиографический список 1. Визинг В.Г. Об оценке хроматического класса p–графа // Дискретный анализ. Сб. науч. тр.– Новосибирск: Ин-т математики СО АН СССР, 1964. – Вып. 3. – С. 25-30.
2. Гэрри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ. – М.: Мир, 1982. – 416 с.
3. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. – 1981. – Vol. 10, № 4. – P. 718-720.
4. Асратян А.С., Камалян Р.Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. – Ереван: Изд-во Ереван. ун-та, 1987. – Вып. 5. – С. 25-34.
5. Севастьянов С.В. Об интервальной раскрашиваемости рёбер двудольного графа // Методы дискретного анализа. – 1990. – Т. 50. – C. 61-72.

Comments are closed.