Refine
Year of publication
- 2018 (2)
Document Type
- In Proceedings (1)
- ZIB-Report (1)
Language
- English (2)
Is part of the Bibliography
- no (2)
Institute
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.
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.