On interval edge d-colouring.pdf Входные данные к расписанию обработки устройств - заданий множества X - в си-стеме устройств-процессоров Y представлены двудольным графом G = (X, Y, E), гдеребро (х,у) присутствует в множестве E тогда и только тогда, когда процессору узапланирована операция над заданием х.Расписание работы устройств будем называть непрерывным, если каждое устрой-ство работает без простоев с момента его включения до выключения.Пусть n - число вершин, Д - наибольшая степень вершины графа G (Д служитнижней границей для длин непрерывных расписаний). Известно, что задача о суще-ствовании непрерывного расписания NP-полна (как и задача о существовании непре-рывного расписания длины Д); в ряде источников она формулируется как задача обинтервальной рёберной раскраске [1,2].Двудольные графы G = (X, Y, E) с небольшими значениями Д и n, не допускаю-щие интервальной раскраски, были построены следующими авторами: С. В. Севастья-новым (Д = 21, n = 28), M. Malafiejcki (Д = 15, n = 19), A. Hertz (Д = 1 4 , n = 23),D. de Werra (Д = 14, n = 21), P. Erdos (Д = 1 3 , n = 27). Отметим, что ни один из этихграфов не является бирегулярным.Построен пример (6, 3)-бирегулярного графа с n = 33, не обладающего интерваль-ной рёберной раскраской в 6 цветов (в [3] доказана NP-полнота задачи об интерваль-ной раскрашиваемости (6, 3)-бирегулярного графа шестью цветами).Теорема 1. Задача об интервальной рёберной раскраске Д цветами остается NP-полной и для двудольных мультиграфов G = (X, Y, E) с | X| = 2.

Скачать электронную версию публикации