Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 128 von 210
Zurück zur Trefferliste

The Graph Segmentation Problem

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-60750
  • We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Stephan SchwartzORCiD, Ralf BorndörferORCiD, Gerald Bartz
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:combinatorial optimization; graph segmentation; toll billing
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:11.01.2016
Schriftenreihe (Bandnummer):ZIB-Report (16-53)
ISSN:1438-0064
Verlagspublikation:INOC 2017 – 8th International Network Optimization Conference
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.