Analyzing Train Time Table Graphs

Cite This

Files in this item

Checksum: MD5:b01282e7ab3d197be845444acf2b1cef

LIEBERS, Annegret, 2001. Analyzing Train Time Table Graphs [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Liebers2001Analy-5425, title={Analyzing Train Time Table Graphs}, year={2001}, author={Liebers, Annegret}, address={Konstanz}, school={Universität Konstanz} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:rights rdf:resource=""/> <dc:language>eng</dc:language> <dc:rights>terms-of-use</dc:rights> <dcterms:hasPart rdf:resource=""/> <dc:format>application/pdf</dc:format> <dc:date rdf:datatype="">2011-03-24T15:55:17Z</dc:date> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:issued>2001</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Liebers, Annegret</dc:creator> <bibo:uri rdf:resource=""/> <dcterms:alternative>Analyse von Fahrplangraphen</dcterms:alternative> <dcterms:abstract xml:lang="deu">The project that this thesis grew out of stems from a cooperation with a subsidiary of the German railway company concerning time tables of trains. Each time table contains the train stations with their arrival and departure times. The abstract representation of the time table data is a directed time table graph: If for two train stations u and v there is at least one time table in which u and v are consecutive stops, then the directed edge (u,v) belongs to the time table graph. The starting point for this thesis is now the following question: For every edge e of a time table graph, decide whether e corresponds to a segment of the physical railroad network, or whether the trains that induce e are passing through one or more train stations without stopping there while traveling along e. This thesis deals with a structural approach for solving this edge classification problem, resulting in the formulation of the bundle recognition problem, a graph theoretic optimization problem. For three versions of the bundle recognition problem NP-completeness results using reductions from 3-Satisfiability or one of its variants can be obtained. In order to still obtain solutions for the underlying application problem, this thesis develops a heuristic for the bundle recognition problem and presents an extensive computational study.</dcterms:abstract> <dcterms:available rdf:datatype="">2011-03-24T15:55:17Z</dcterms:available> <dcterms:title>Analyzing Train Time Table Graphs</dcterms:title> <dcterms:isPartOf rdf:resource=""/> <dc:contributor>Liebers, Annegret</dc:contributor> <dspace:hasBitstream rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

liebers-diss.pdf 220

This item appears in the following Collection(s)

Search KOPS


My Account