Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/344033| Заглавие документа: | Разбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4 |
| Другое заглавие: | Partitioning the edge set of a bipartite graph Into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle |
| Авторы: | Дугинов, О.И. Химич, С.С. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2022 |
| Издатель: | Национальная академия наук Беларуси |
| Библиографическое описание источника: | Весці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-матэматычных навук.2022; Т. 58(2): С. 155-168. |
| Аннотация: | Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка <i>n</i> за время <i>O</i>(<i>n</i> log <i>n</i>). Выделены трудноразрешимые случаи задачи. |
| Аннотация (на другом языке): | In this paper, we study the computational complexity for a problem of partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple cycle of order 4 in special graph classes. This problem is NP-hard and finds application in organizing the distribution of network packets over communication channels in the process of transmission from one router to another. We develop an <i>O</i>(<i>n</i>log<i>n</i>) algorithm for solving that problem in a class of n order trees. Intractable cases of the problem are identified. |
| URI документа: | https://elib.bsu.by/handle/123456789/344033 |
| DOI документа: | 10.29235/1561-2430-2022-58-2-155-168 |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 640-1302-1-SM.pdf | 841,98 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.