Publikation:

Recognizing Bundles in Time Table Graphs : a Structural Approach

Lade...
Vorschaubild

Dateien

preprint_096_02.pdf
preprint_096_02.pdfGröße: 1002.48 KBDownloads: 275

Datum

2000

Autor:innen

Liebers, Annegret
Wagner, Dorothea
Weihe, Karsten

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

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

Publikationstyp
Preprint
Publikationsstatus
Published

Erschienen in

Zusammenfassung

We are dealing with an application problem arising in a cooperation with the national German railway company which occurs in the analysis of time table data. The purpose is to infer the underlying railroad network and the actual travel route of the trains when only their time tables are known. The structural basis of our considerations in this paper is a directed graph constructed from train time tables, where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. Determining the travel route of trains corresponds to an edge classification problem in this graph. Exploiting the structure of this graph, we approach the edge classification problem by locating vertices that intuitively correspond to train stations where the underlying railroad network branches into several directions, and that induce a partition of the edge set into bundles.

We describe the modeling process of the classification problem resulting in the bundle recognition problem. Given the NP-hardness of the corresponding optimization problem, we present a heuristic that exploits among other things the geometry of the embedded directed graph. We perform a computational study using time table data from 13 European countries.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690LIEBERS, Annegret, Dorothea WAGNER, Karsten WEIHE, 2000. Recognizing Bundles in Time Table Graphs : a Structural Approach
BibTex
@unpublished{Liebers2000Recog-6447,
  year={2000},
  title={Recognizing Bundles in Time Table Graphs : a Structural Approach},
  author={Liebers, Annegret and Wagner, Dorothea and Weihe, Karsten}
}
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/6447">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Liebers, Annegret</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:46Z</dc:date>
    <dc:rights>terms-of-use</dc:rights>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6447"/>
    <dcterms:title>Recognizing Bundles in Time Table Graphs : a Structural Approach</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:abstract xml:lang="eng">We are dealing with an application problem arising in a cooperation with the national German railway company which occurs in the analysis of time table data. The purpose is to infer the underlying railroad network and the actual travel route of the trains when only their time tables are known. The structural basis of our considerations in this paper is a directed graph constructed from train time tables, where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. Determining the travel route of trains corresponds to an edge classification problem in this graph. Exploiting the structure of this graph, we approach the edge classification problem by locating vertices that intuitively correspond to train stations where the underlying railroad network branches into several directions, and that induce a partition of the edge set into bundles.&lt;br /&gt;&lt;br /&gt;We describe the modeling process of the classification problem resulting in the bundle recognition problem. Given the NP-hardness of the corresponding optimization problem, we present a heuristic that exploits among other things the geometry of the embedded directed graph. We perform a computational study using time table data from 13 European countries.</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:issued>2000</dcterms:issued>
    <dc:creator>Weihe, Karsten</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:46Z</dcterms:available>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6447/1/preprint_096_02.pdf"/>
    <dc:contributor>Liebers, Annegret</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6447/1/preprint_096_02.pdf"/>
    <dc:contributor>Weihe, Karsten</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:format>application/pdf</dc:format>
  </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

Finanzierungsart

Kommentar zur Publikation

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