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

        Uniform sampling of bi-colored random graph

        Thumbnail
        View/Open
        Thesis (A.lin).pdf (826.0Kb)
        Publication date
        2022
        Author
        Lin, Andi
        Metadata
        Show full item record
        Summary
        We propose a near-linear complexity algorithm for uniform sampling of simple random graphs with bi-colored edges imposed by two given colored degree sequences. This problem is also known as three-colour discrete tomography and is closely related to the sequence packing problem, both of which are known to be NP hard in the general setting. That being said, our algorithm provides a fast means of asymptotically uniform sampling for large graphs.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/496
        Collections
        • Theses
        Utrecht university logo