## René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko.
Parameterized algorithms and data reduction for safe convoy routing.
In *Proceedings of the 18th Workshop on Algorithmic Approaches
for Transportation Modeling, Optimization, and Systems (ATMOS'18), Helsinki,
Finland*, volume 65 of *OpenAccess Series in Informatics (OASIcs)*, pages
10:1–10:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.

We study a problem that models safely routing a
convoy through a transportation network, where any
vertex adjacent to the travel path of the convoy
requires additional precaution: Given a graph
G=(V,E), two vertices s,t∈V, and two integers k,ℓ,
we search for a simple s-t-path with at most k
vertices and at most ℓ neighbors. We study the
problem in two types of transportation networks:
graphs with small crossing number, as formed by road
networks, and tree-like graphs, as formed by
waterways. For graphs with constant crossing number,
we provide a subexponential 2^O(√n)-time algorithm
and prove a matching lower bound. We also show a
polynomial-time data reduction algorithm that
reduces any problem instance to an equivalent
instance (a so-called problem kernel) of size
polynomial in the vertex cover number of the input
graph. In contrast, we show that the problem in
general graphs is hard to preprocess. Regarding
tree-like graphs, we obtain a 2^O(tw)⋅ℓ^2⋅n-time
algorithm for graphs of treewidth tw, show that
there is no problem kernel with size polynomial in
tw, yet show a problem kernel with size polynomial
in the feedback edge number of the input graph.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*