90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Filtern
Erscheinungsjahr
- 2016 (1) (entfernen)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- combinatorial optimization (1) (entfernen)
Institut
- Mathematics of Transportation and Logistics (1) (entfernen)
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.