Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle
https://doi.org/10.29235/1561-2430-2022-58-2-155-168
Abstract
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.
Supporting agencies: 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)
About the Authors
O. I. Duginov
Belarusian State University
Belarus
Belarus
Oleg I. Duginov – Ph. D. (Physics and Mathematics), Associate Professor of the Department of Discrete Mathematics and Algorithmics
4, Nezavisimosti Ave., 220030, Minsk
S. S. Khimich
Belarusian State University
Belarus
Belarus
Semyon S. Khimich – Student at Faculty of Applied Mathematics and Computer Science
4, Nezavisimosti Ave., 220030, Minsk
References
1. 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.
2. Hochbaum D. S., Levin A. Covering the edges of bipartite graphs using K2,2 graphs. Theoretical Computer Science, 2010, vol. 411, pp. 1–9.
3. Dor 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/s0097539792229507
4. Holyer 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/0210054
5. Dyer 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-3
6. Golumbic 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.3190020209
7. Goh 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
Review
Views:
682
Email this article 