OR2017 Abstract Submission

The Graph Segmentation Problem

Invited abstract in session WB-4: Graphs and Complexity, stream Graphs and Networks.

Wednesday, 11:00-12:30
Room: WGS|104

Authors (first author is the speaker)

1. Stephan Schwartz
Zuse Institute Berlin
2. Leonardo Balestrieri
Freie Universität Berlin
3. Ralf Borndörfer
Optimization, Zuse-Institute Berlin


We study a novel graph theoretical problem arising in the automatic billing of a toll network. The graph segmentation problem (GSP) is to cover a family of user paths in a given network with a set of disjoint segments (which are also paths). We investigate structural properties of the problem and derive tight bounds for the utility of an optimal segmentation. While the GSP is NP-hard in general, special cases can be solved in polynomial time. We also give an integer programming formulation that benefits from the results of our structural analysis. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.


Status: accepted

Back to the list of papers