On distributed forest decomposition of graphs with bounded arboricity

摘要

Efficient data representation and secure communication are both crucial problems in the modern world. Those problems are both actual in the distributed context as well. In this article we focus on forest decomposition of graphs in distributed networks in order to impact those two problems. Currently, there are several existing algorithms that decompose generic or restricted graph instances with both bounded degree or arboricity into edge-disjoint forests with sublogarithmic running time. We propose a modification of an algorithm that was already devised before, such that it is possible to implement the algorithm and conduct an experiment over simulated graph instances from different graph families. Finally, we compare achieved experimental results with theoretical estimates. We also discuss the application of the algorithm for solving the problem of efficient graph representation and secure data communication in distributed networks. More specifically, the impact of the algorithm on implementing an implicit representation of graphs, overcoming man-in-the-middle attacks and implementing efficient load balancing of networks.