азбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4
2022
Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи.
Дугинов О. И., Химич С. С. азбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4. Известия Национальной академии наук Беларуси. Серия физико-математических наук. 2022;58(2):155-168. https://doi.org/10.29235/1561-2430-2022-58-2-155-168
Цитирование
Список литературы