An evaluation of dynamic algorithms for incremental graph connectivity

Abstract: Union-Find is a family of algorithms that store disjoint sets of connected data. Allowing operations such as: a function Union that unites sets through union and a function Find that finds the set representative, it becomes an obvious solution to the dynamic problem of incremental connectivity. By creating sets containing graph vertices, information regarding what vertices have edges between them can be kept. Each connected component in a graph is in this way represented as separate sets. Through unions, new vertices can be added to these sets at any time. Through the described structure, dynamic graphs, that increment at any time by edge additions, can be handled. Different Union-Find algorithms are usually denoted by combining one Union optimization with one Find optimization. This thesis presents an experiment where three classical Union-Find algorithms, LRPC, LRPH and LRPS, are tested in terms of real-time efficiency. The results show that throughout all tests, LRPC performs the worst, LRPH and LRPS take turns being more effective for bigger graphs, and for smaller graphs, the Naive version with no optimizations at all is the most effective.