6929
2018
eng
35
44
64
conferenceobject
0
--
--
--
The Graph Segmentation Problem
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.
INOC 2017 – 8th International Network Optimization Conference
yes
Electronic Notes in Discrete Mathematics
urn:nbn:de:0297-zib-60750
Ralf Borndörfer
Stephan Schwartz
Stephan Schwartz
Gerald Bartz
Mathematical Optimization
Borndörfer, Ralf
Schwartz, Stephan
MODAL-RailLab
TOLLCONTROLOPT
MODAL-Gesamt