2026-07-23T15:27:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12100 2024-03-06T10:49:21Z ddc:004 open_access

Fast and Stable Repartitioning of Road Networks Buchhold, Valentin Delling, Daniel Schieferdecker, Dennis Wegner, Michael Graph repartitioning stable partitions road networks algorithm engineering We study the problem of graph partitioning for evolving road networks. While the road network of the world is mostly stable, small updates happen on a relatively frequent basis, as can been observed with the OpenStreetMap project (http://www.openstreetmap.org). For various reasons, professional applications demand the graph partition to stay roughly the same over time, and that changes are limited to areas where graph updates occur. In this work, we define the problem, present algorithms to satisfy the stability needs, and evaluate our techniques on continental-sized road networks. Besides the stability gains, we show that, when the changes are low and local, running our novel techniques is an order of magnitude faster than running graph partitioning from scratch. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Valentin Buchhold and Daniel Delling and Dennis Schieferdecker and Michael Wegner 2020 Is Part Of LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2020.26 urn:nbn:de:0030-drops-121000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode