Analyzing Train Time Table Graphs
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
LIEBERS, Annegret, 2001. Analyzing Train Time Table Graphs [Dissertation]. Konstanz: University of KonstanzBibTex
@phdthesis{Liebers2001Analy-5425,
year={2001},
title={Analyzing Train Time Table Graphs},
author={Liebers, Annegret},
address={Konstanz},
school={Universität Konstanz}
}RDF
<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/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.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.uni-konstanz.de/server/rdf/resource/123456789/5425">
<dcterms:alternative>Analyse von Fahrplangraphen</dcterms:alternative>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Liebers, Annegret</dc:creator>
<dcterms:issued>2001</dcterms:issued>
<dc:contributor>Liebers, Annegret</dc:contributor>
<dc:language>eng</dc:language>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:55:17Z</dc:date>
<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>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5425/1/liebers-diss.pdf"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5425"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dc:format>application/pdf</dc:format>
<dc:rights>terms-of-use</dc:rights>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5425/1/liebers-diss.pdf"/>
<dcterms:title>Analyzing Train Time Table Graphs</dcterms:title>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:55:17Z</dcterms:available>
</rdf:Description>
</rdf:RDF>
