On Finding Subpaths With High Demand
Please always quote using this URN: urn:nbn:de:0297-zib-69280
- 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, Leonardo Balestrieri, Ralf BorndörferORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 2018/06/19 |
| Series (Serial Number): | ZIB-Report (18-27) |
| ISSN: | 1438-0064 |
| Published in: | Operations Research 2017 |
