| dc.rights.license | CC-BY-NC-ND | |
| dc.contributor.advisor | Kryven, I.V. | |
| dc.contributor.author | Lin, Andi | |
| dc.date.accessioned | 2022-02-15T00:00:36Z | |
| dc.date.available | 2022-02-15T00:00:36Z | |
| dc.date.issued | 2022 | |
| dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/496 | |
| dc.description.abstract | 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. | |
| dc.description.sponsorship | Utrecht University | |
| dc.language.iso | EN | |
| dc.subject | 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 | |
| dc.title | Uniform sampling of bi-colored random graph | |
| dc.type.content | Master Thesis | |
| dc.rights.accessrights | Open Access | |
| dc.subject.courseuu | Mathematical Sciences | |
| dc.thesis.id | 2262 | |
