View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Bitmap Compression Techniques for Large Graph Treewidth Computation

        Thumbnail
        View/Open
        Thesis_JasperMunnichs.pdf (24.52Mb)
        Publication date
        2021
        Author
        Munnichs, Jasper
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/217
        Collections
        • Theses
        Utrecht university logo