@misc{Elijazyfer2018, type = {Master Thesis}, author = {Elijazyfer, Ziena}, title = {L{\"a}ngenbeschr{\"a}nkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung}, year = {2018}, language = {de} } @misc{Schreck2018, type = {Master Thesis}, author = {Schreck, Vanessa}, title = {Algorithmic Analysis of the Graph Segmentation Problem}, year = {2018}, language = {en} } @misc{SchwartzBalestrieriBorndoerfer2018, author = {Schwartz, Stephan and Balestrieri, Leonardo and Bornd{\"o}rfer, Ralf}, title = {On Finding Subpaths With High Demand}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69280}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{SchwartzBorndoerferBalestrieri2018, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Balestrieri, Leonardo}, title = {On Finding Subpaths With High Demand}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, pages = {355 -- 360}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{BorndoerferSchwartzBartz2018, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Bartz, Gerald}, title = {The Graph Segmentation Problem}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, pages = {35 -- 44}, year = {2018}, 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} }