Metraipolis › archive › dc_6ca660efa953
Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas — arXiv:2608.09472
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.09472
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T06:49:38.239Z
- SHA-256 of the archived text
d494476daf6b5b5fe7fa948ebc4f525d2e863c2164a128e5d06230ba51bd642e- Stable URL of this page
https://metraipolis.com/documento/dc_6ca660efa953
How to cite
Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas — arXiv:2608.09472 — arXiv (en), https://arxiv.org/abs/2608.09472 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6ca660efa953 (Metraipolis archive dc_6ca660efa953, sha256 d494476daf6b5b5fe7fa948ebc4f525d2e863c2164a128e5d06230ba51bd642e)
BibTeX
@misc{dc6ca660efa953,
title = {Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas — arXiv:2608.09472},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.09472},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6ca660efa953; sha256 d494476daf6b5b5fe7fa948ebc4f525d2e863c2164a128e5d06230ba51bd642e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09472. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce the \emph{Safe Bicycle Network with Bounded Detours} (\emph{SBNBD}) problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph with safe and unsafe edges, edge lengths, upgrade costs, terminal pairs, a budget, and a detour factor $\alpha$, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most $\alpha$ times its shortest-path distance in the original network. We study SBNBD from a parameterized perspective. We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three, and complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. We show fixed-parameter tractability for the number of unsafe edges and prove matching SETH-based lower bounds, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main structural result maps any instance to an equivalent instance with $O(\mathrm{fes}+p)$ vertices and edges, where $\mathrm{fes}$ is the feedback edge number and $p$ the number of terminal pairs; this yields fixed-parameter tractability for $\mathrm{fes}+p$. Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities and their surroundings. The instances have small treewidth upper bounds and moderate feedback edge structure. Preprocessing based on the $\mathrm{fes}+p$ reduction and tree-decomposition-based cut generation both improve exact solving, especially on harder instances. Experiments with different detour factors show that increasing $\alpha$ can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours. Overall, structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-11 in cs.MA).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Multiagent Systems (cs.MA).
Pagina del lavoro: https://arxiv.org/abs/2608.09472 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T06:45:31.718Z dalla pagina https://arxiv.org/catchup/cs.MA/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).