License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2010.61
URN: urn:nbn:de:0030-drops-27508
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2750/
Go to the corresponding OASIcs Volume Portal

Flier, Holger ; Mihalák, Matús ; Schöbel, Anita ; Widmayer, Peter ; Zych, Anna

Vertex Disjoint Paths for Dispatching in Railways

pdf-format:
6.pdf (0.5 MB)

Abstract

We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.

BibTeX - Entry

@InProceedings{flier_et_al:OASIcs:2010:2750,
  author =	{Holger Flier and Mat{\'u}s Mihal{\'a}k and Anita Sch{\"o}bel and Peter Widmayer and Anna Zych},
  title =	{{Vertex Disjoint Paths for Dispatching in Railways}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{61--73},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Thomas Erlebach and Marco L{\"u}bbecke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2750},
  URN =		{urn:nbn:de:0030-drops-27508},
  doi =		{10.4230/OASIcs.ATMOS.2010.61},
  annote =	{Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation}
}

Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation
Collection: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)
Issue Date: 2010
Date of publication: 01.09.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI