TY - CONF
A1 - Borndörfer, Ralf
A1 - Schwartz, Stephan
A1 - Bartz, Gerald
T1 - The Graph Segmentation Problem
T2 - INOC 2017 – 8th International Network Optimization Conference
N2 - 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.
Y1 - 2018
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6929
VL - 64
SP - 35
EP - 44
ER -