Type of Publication:  Dissertation 
URI (citable link):  http://nbnresolving.de/urn:nbn:de:bsz:352opus6675 
Author:  Liebers, Annegret 
Year of publication:  2001 
Title in another language:  Analyse von Fahrplangraphen 
Summary: 
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 NPcompleteness results using reductions from 3Satisfiability 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.

Examination date (for dissertations):  Jul 20, 2000 
Dissertation note:  Doctoral dissertation, University of Konstanz 
CCS Classification:  F.2.2; G.2.3 
Subject (DDC):  004 Computer Science 
Controlled Keywords (GND):  Fahrplan, Graph, Kombinatorische Optimierung, NPvollständiges Problem, Heuristik 
Keywords:  Time Table, Graph, Combinatorial Optimization, NPcomplete Problem, Heuristic 
Link to License:  Terms of use 
LIEBERS, Annegret, 2001. Analyzing Train Time Table Graphs [Dissertation]. Konstanz: University of Konstanz
@phdthesis{Liebers2001Analy5425, title={Analyzing Train Time Table Graphs}, year={2001}, author={Liebers, Annegret}, address={Konstanz}, school={Universität Konstanz} }
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.unikonstanz.de/rdf/resource/123456789/5425"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:rights rdf:resource="https://kops.unikonstanz.de/page/termsofuse"/> <dc:language>eng</dc:language> <dc:rights>termsofuse</dc:rights> <dcterms:hasPart rdf:resource="https://kops.unikonstanz.de/bitstream/123456789/5425/1/liebersdiss.pdf"/> <dc:format>application/pdf</dc:format> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110324T15:55:17Z</dc:date> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dcterms:issued>2001</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Liebers, Annegret</dc:creator> <bibo:uri rdf:resource="http://kops.unikonstanz.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 NPcompleteness results using reductions from 3Satisfiability 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="http://www.w3.org/2001/XMLSchema#dateTime">20110324T15:55:17Z</dcterms:available> <dcterms:title>Analyzing Train Time Table Graphs</dcterms:title> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Liebers, Annegret</dc:contributor> <dspace:hasBitstream rdf:resource="https://kops.unikonstanz.de/bitstream/123456789/5425/1/liebersdiss.pdf"/> </rdf:Description> </rdf:RDF>
liebersdiss.pdf  220 