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

        Parameterized Algorithms in a Streaming Setting

        Thumbnail
        View/Open
        thesis.pdf (1.174Mb)
        Publication date
        2020
        Author
        Oostveen, J.J.
        Metadata
        Show full item record
        Summary
        Saving large graphs in memory can be problematic. Streaming the graph provides a solution, where the graph arrives as a stream of edges. Different streaming models can be used to assume a variable amount of information present in the stream. In combination with parameterized complexity, we can find algorithms using sublinear memory, where for non-parameterized algorithms it can be proven that we require linear memory. In this work, we investigate a broad range of problems in the streaming setting, including varying approaches to solve them. Different approaches can lead to an interesting trade-off in the number of times we inspect the stream and the memory usage. Hence, we explore both kernelization and direct algorithmic approaches for solving problems such as Pi-free Deletion, Pi-free Editing, Vertex Cover, and Edge Dominating Set. In terms of parameterization, we focus on using the parameter vertex cover, but we will also see solution size and tree-depth being used. We will see a range of upper bound results, which are partially direct adaptations of non-streaming algorithms, and partially new work. We will also see some lower bounds on the memory use given the number of passes we make over the stream.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/37120
        Collections
        • Theses
        Utrecht university logo