Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/291303| Заглавие документа: | РАЗБИЕНИЕ РЕБЕР ДВУДОЛЬНОГО ГРАФА НА НАИМЕНЬШЕЕ ЧИСЛО ПОДГРАФОВ, ИЗОМОРФНЫХ ПОДГРАФАМ ПРОСТОГО ЦИКЛА ПОРЯДКА 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 |
| Издатель: | Belaruskaya Navuka |
| Библиографическое описание источника: | Proc Natl Acad Sci Belarus Phys Math Ser 2022;58(2):155-168. |
| Аннотация: | Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи. |
| Аннотация (на другом языке): | 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 O(nlogn) 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/291303 |
| DOI документа: | 10.29235/1561-2430-2022-58-2-155-168 |
| Scopus идентификатор документа: | 85135262077 |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 640-1302-1-SM.pdf | 841,98 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.