@misc{SchwartzBorndoerferBartz, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Bartz, Gerald}, title = {The Graph Segmentation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60750}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferSchwartzBartz, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Bartz, Gerald}, title = {The Graph Segmentation Problem}, series = {INOC 2017 - 8th International Network Optimization Conference}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, pages = {35 -- 44}, abstract = {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.}, language = {en} }