Bitmap Compression Techniques for Large Graph Treewidth Computation

Abstract

In this thesis we investigate whether bitmap compression techniques could be useful data structures to represent vertex sets, for treewidth algorithms on large graphs. We consider bitmap compression techniques Roaring Bitmap and EWAH, and compare them with two more commonly used graph data structures: the bitmap and the array of integers. We investigate the behaviour of the data structures in two experiments. In the first, we investigate their computation time and memory consumption of typical vertex sets in the computation of separated components. In the second, we compare their performance on the Minimal Minimum Degree algorithm. We find that the array of integers representation performs best. However, as typical vertex sets that the data structures have to deal with get denser and more diverse, we observe that Roaring Bitmap starts to perform better.