vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2022-58-2-155-168vestifm-640Research ArticleМАТЕМАТИКАMATHEMATICSазбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycleДугиновО. И.DuginovO. I.

Дугинов Олег Иванович – кандидат физико-математических наук, доцент кафедры дискретной математики и алгоритмики

пр. Независимости, 4, 220030, Минск

Oleg I. Duginov – Ph. D. (Physics and Mathematics), Associate Professor of the Department of Discrete Mathematics and Algorithmics

4, Nezavisimosti Ave., 220030, Minsk

oduginov@gmail.comХимичС. С.KhimichS. S.

Химич Семен Сергеевич – студент, факультет прикладной математики и информатики

пр. Независимости, 4, 220030, Минск

Semyon S. Khimich – Student at Faculty of Applied Mathematics and Computer Science

4, Nezavisimosti Ave., 220030, Minsk

semyonximich@gmail.comBelarusian State UniversityBelarusБелорусский государственный университетBelarusian State University202205072022582155168Copyright © Дугинов О.И., Химич С.С., 20222022Дугинов О.И., Химич С.С.Duginov O.I., Khimich S.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/640

Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 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.

разбиение множества ребер графадеревьяподграфы простого цикла порядка 4partitioning the edge set of a graphtreessubgraphs of a simple cycle of order 4Исследование первым автором выполнено при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проект № Ф21РМ-001).The research was carried out by the first author under the financial support of the Belarusian Republican Foundation for Fundamental Research (project no. Ф21РМ-001)ReferencesЛекции по теории графов / В. А. Емеличев [и др.]. – М.: УРСС, 2019. – 390 с.Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on Graph Theory. Manncheim, Vena, Zurich, B. I. Wissenschaftsferlfg, 1994. 364 p.Hochbaum, D. S. Covering the edges of bipartite graphs using K2,2 graphs / D. S. Hochbaum, A. Levin // Theor. Comput. Sci. – 2010. – Vol. 411. – P. 1–9.Hochbaum D. S., Levin A. Covering the edges of bipartite graphs using K2,2 graphs. Theoretical Computer Science, 2010, vol. 411, pp. 1–9.Dor, D. Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture / D. Dor, M. Tarsi // SIAM J. Comput. – 1997. – Vol. 26, № 4. – P. 1166–1187. https://doi.org/10.1137/s0097539792229507Dor D., Tarsi M. Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture. SIAM Journal on Computing, 1997, vol. 26, no. 4, pp. 1166–1187. https://doi.org/10.1137/s0097539792229507Holyer, I. The NP-completeness of some edge partition problems / I. Holyer // SIAM SIAM J. Comput. – 1981. – Vol. 10, № 4. – P. 713–717. https://doi.org/10.1137/0210054Holyer I. The NP-completeness of some edge partition problems. SIAM Journal on Computing, 1981, vol. 10, no. 4, pp. 713–717. https://doi.org/10.1137/0210054Dyer, M. E. On the complexity of partitioning graphs into connected subgraphs / M. E. Dyer, A. M. Frieze // Discrete Appl. Math. – 1985. – Vol. 10, № 2. – P. 139–153. https://doi.org/10.1016/0166-218x(85)90008-3Dyer M. E., Frieze A. M. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 1985, vol. 10, no. 2, pp. 139–153. https://doi.org/10.1016/0166-218x(85)90008-3Golumbic, M. C. Perfect elimination and chordal bipartite graphs / M. C. Golumbic, G. F. Goss // J. Graph Theory. – 1978. – Vol. 2, № 2. – P. 155–163. https://doi.org/10.1002/jgt.3190020209Golumbic M. C., Goss G. F. Perfect elimination and chordal bipartite graphs. Journal of Graph Theory, 1978, vol. 2, no. 2, pp. 155–163. https://doi.org/10.1002/jgt.3190020209Goh, L. Recognition of perfect elimination bipartite graphs / L. Goh, D. Rotem // Inf. Process. Lett. – 1982. – Vol. 15, № 4. – P. 179–182. https://doi.org/10.1016/0020-0190(82)90101-6Goh L., Rotem D. Recognition of perfect elimination bipartite graphs. Information Processing Letters, 1982, vol. 15, no. 4, pp. 179–182. https://doi.org/10.1016/0020-0190(82)90101-6

The authors declare that there are no conflicts of interest present.