{"id":"arxiv/2606.14128","url":"https://arxiv.org/abs/2606.14128","tags":["cs.DS","math.CO","math.OC"],"score":0,"title":"Designing Efficient and Reachable Routes: The $k$-Step-Central Shortest Path Problem","domain":"cs.DS","source":"arxiv","authors":["Johnson Phosavanh","Dmytro Matsypura"],"reviews":0,"subject":"cs.DS","summary":"Designing rapid transportation routes requires balancing efficiency and reachability. Shortest-path models ensure direct, cost-efficient routes but ignore coverage, while centrality-based approaches maximize accessibility but do not enforce operational constraints. We study the problem of selecting a shortest path that maximizes reachability, measured as the number of nodes within a fixed distance of the path. To do this, we introduce the $k$-Step-Central Shortest Path problem and analyse its structural properties. We show that optimal solutions on unweighted graphs can be found in…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-12","reactions":{}}