dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Bisseling, prof. dr. R.H. | |
dc.contributor.author | Reijnders, B.J.H.R. | |
dc.date.accessioned | 2018-05-16T17:01:07Z | |
dc.date.available | 2018-05-16T17:01:07Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/29036 | |
dc.description.abstract | We propose a new pre-processing heuristic for partitioning road networks using multilevel graph partitioning (MGP) implementations. This heuristic is based on the notion that in road networks, edges with high betweenness centralities are often excellent cut-edge candidates. We pre-process the network in such a way that edges with low-betweenness centralities are contracted in the coarsening phase of an MGP algorithm, such that initial partitionings are formed along edges with high betweenness centralities. We find that our implementation of this pre-processing method significantly improves the edgecut when applied to national road networks partitioned using METIS. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 1623230 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.title | Pre-processing Road Networks for Graph Partitioning Using Edge-Betweenness Centrality | |
dc.type.content | Bachelor Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | road networks; multilevel graph partitioning; betweenness centrality; natural cuts; pre-processing; graph partitioning heuristic; | |
dc.subject.courseuu | UCU Liberal Arts and Sciences - Sciences: Mathematics | |