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.
Author: | Stephan SchwartzORCiD, Ralf BorndörferORCiD, 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 |