On Finding Subpaths With High Demand

  • We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Stephan Schwartz, Ralf Borndörfer, Leonardo Balestrieri
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2017
First Page:355
Last Page:360
Publisher:Springer International Publishing
Year of first publication:2018
Preprint:urn:nbn:de:0297-zib-69280