Preview

Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series

Advanced search

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.

Views: 662


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)