Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 8 of 18
Back to Result List

On Finding Subpaths With High Demand

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Stephan SchwartzORCiD, Ralf BorndörferORCiD, Leonardo Balestrieri
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2017
First Page:355
Last Page:360
Publisher:Springer International Publishing
Year of first publication:2018
Preprint:urn:nbn:de:0297-zib-69280
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.