Analyzing Train Time Table Graphs

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:b01282e7ab3d197be845444acf2b1cef

LIEBERS, Annegret, 2001. Analyzing Train Time Table Graphs

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

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/5425"> <dc:rights>deposit-license</dc:rights> <dc:language>eng</dc:language> <dc:format>application/pdf</dc:format> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:55:17Z</dc:date> <dcterms:issued>2001</dcterms:issued> <dc:creator>Liebers, Annegret</dc:creator> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5425"/> <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:title>Analyzing Train Time Table Graphs</dcterms:title> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103416863-3868037-7"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:55:17Z</dcterms:available> <dc:contributor>Liebers, Annegret</dc:contributor> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

liebers-diss.pdf 78

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto