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