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

        An overview of different kernelization algorithms for the cluster editing problem

        Thumbnail
        View/Open
        Scriptie Joost Besseling.pdf (342.5Kb)
        Publication date
        2016
        Author
        Besseling, J.P.
        Metadata
        Show full item record
        Summary
        In the cluster editing problem, we try to transform a given graph G into a disjoint union of cliques using less than k edge modifications. In this paper we will focus on the kernelization of the input (G; k). Kernelization is a pre-processing step in which the size of a given input (G; k) is reduced to a kernel (G'; k' ) with |G'| < |G| and k' < k. After the kernelization, the kernel is processed by the normal algorithm, and the optimal solution should be the same as (or easy to find from) the optimal solution of the original problem. In this paper we will give an overview of di erent kernelization algorithms for the cluster editing problem.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/23423
        Collections
        • Theses
        Utrecht university logo