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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Stephan Schwartz, Leonardo Balestrieri, Ralf BorndörferORCiD
Document Type:ZIB-Report
Date of first Publication:2018/06/19
Series (Serial Number):ZIB-Report (18-27)
Published in:Operations Research 2017