Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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 Statistics - number of accesses to the document
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)
Published in:Operations Research 2017
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.