Recognizing Bundles in Time Table Graphs : a Structural Approach


Dateien zu dieser Ressource

Prüfsumme: MD5:9a20abfde580f1c9ec40a971ed3c1b2e

LIEBERS, Annegret, Dorothea WAGNER, Karsten WEIHE, 2000. Recognizing Bundles in Time Table Graphs : a Structural Approach

@unpublished{Liebers2000Recog-6447, title={Recognizing Bundles in Time Table Graphs : a Structural Approach}, year={2000}, author={Liebers, Annegret and Wagner, Dorothea and Weihe, Karsten} }

2000 Weihe, Karsten eng 2011-03-24T16:12:46Z Liebers, Annegret Wagner, Dorothea Recognizing Bundles in Time Table Graphs : a Structural Approach Liebers, Annegret 2011-03-24T16:12:46Z We are dealing with an application problem arising in a cooperation with the national German railway company which occurs in the analysis of time table data. The purpose is to infer the underlying railroad network and the actual travel route of the trains when only their time tables are known. The structural basis of our considerations in this paper is a directed graph constructed from train time tables, where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. Determining the travel route of trains corresponds to an edge classification problem in this graph. Exploiting the structure of this graph, we approach the edge classification problem by locating vertices that intuitively correspond to train stations where the underlying railroad network branches into several directions, and that induce a partition of the edge set into bundles.<br /><br />We describe the modeling process of the classification problem resulting in the bundle recognition problem. Given the NP-hardness of the corresponding optimization problem, we present a heuristic that exploits among other things the geometry of the embedded directed graph. We perform a computational study using time table data from 13 European countries. application/pdf Wagner, Dorothea deposit-license Weihe, Karsten

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

preprint_096_02.pdf 135

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto