RT - article
SR - Electronic
T1 - азбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4
JF - Известия Национальной академии наук Беларуси. Серия физико-математических наук
SP - 2022-07-05
DO - 10.29235/1561-2430-2022-58-2-155-168
A1 - Дугинов О. И., 
A1 - Химич С. С., 
YR - 2022
UL - https://www.academjournals.by/publication/12727
AB - Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи.