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