2026-08-16T22:14:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2750 2024-03-06T10:28:43Z ddc:004 open_access

Vertex Disjoint Paths for Dispatching in Railways Flier, Holger Mihalák, Matús Schöbel, Anita Widmayer, Peter Zych, Anna algorithms approximation complexity graph theory railways routing transportation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Holger Flier and Matús Mihalák and Anita Schöbel and Peter Widmayer and Anna Zych 2010 Is Part Of OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2010.61 urn:nbn:de:0030-drops-27508 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.61 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode