Skip to content

Vilin97/CS591-Project

 
 

Repository files navigation

This is a repo of a semester-long project conducted by Vasily Ilin and Tanin Tyler Lux as part of the Spring 2020 iteration of CS591 -- Graph Mining, at Boston University. We implement and benchmark the Dynamic Connectivity data structure from a 1995 paper by Henzinger and King called "Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation".

Go to report/Fully_Dynamic_Connectivity_Report.pdf for the description and the report. If you want to test it out, run Demo.py. It will set up a random graph drawn from G(n,p), and benchmark the Dynamic Connectivity data structure against BFS, using two different implementations of a balanced binary tree: RNB and AVL trees.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%