Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/291303| Title: | РАЗБИЕНИЕ РЕБЕР ДВУДОЛЬНОГО ГРАФА НА НАИМЕНЬШЕЕ ЧИСЛО ПОДГРАФОВ, ИЗОМОРФНЫХ ПОДГРАФАМ ПРОСТОГО ЦИКЛА ПОРЯДКА 4 |
| Other Titles: | PARTITIONING THE EDGE SET OF A BIPARTITE GRAPH INTO THE MINIMAL NUMBER OF SUBGRAPHS ISOMORPHIC TO THOSE OF A SIMPLE 4 ORDER CYCLE |
| Authors: | Дугинов, О. И. Химич, С. С. |
| Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Issue Date: | 2022 |
| Publisher: | Belaruskaya Navuka |
| Citation: | Proc Natl Acad Sci Belarus Phys Math Ser 2022;58(2):155-168. |
| Abstract: | Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи. |
| Abstract (in another language): | 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 |
| Licence: | info:eu-repo/semantics/openAccess |
| Appears in Collections: | Статьи факультета прикладной математики и информатики |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 640-1302-1-SM.pdf | 841,98 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.