Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces four novel fully dynamic parallel algorithms for maintaining rooted spanning forests in response to batch edge insertions and deletions, addressing a significant gap in the literature where such parallel algorithms have been largely unexplored. The methods leverage GPU capabilities to achieve impressive throughput rates of 2 million insertions and 1.4 million deletions per second on real-world graphs. These results not only enhance the efficiency of dynamic graph updates but also have implications for applications in network maintenance and routing adjustments.
Achieving 2 million edge insertions per second on GPUs could revolutionize how we manage dynamic networks in real-time applications.
Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimum-weighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms.