Publikation:

Analyzing Train Time Table Graphs

Lade...
Vorschaubild

Dateien

liebers-diss.pdf
liebers-diss.pdfGröße: 16.2 MBDownloads: 387

Datum

2001

Autor:innen

Liebers, Annegret

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Analyse von Fahrplangraphen
Publikationstyp
Dissertation
Publikationsstatus
Published

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)
004 Informatik

Schlagwörter

Time Table, Graph, Combinatorial Optimization, NP-complete Problem, Heuristic

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690LIEBERS, Annegret, 2001. Analyzing Train Time Table Graphs [Dissertation]. Konstanz: University of Konstanz
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

July 20, 2000
Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen