Parameterized algorithms and data reduction for safe convoy routing

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

Abstract

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-tpath 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 2O(√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 2O(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.

Original languageEnglish
Title of host publication18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume65
ISBN (Print)9783959770965
DOIs
Publication statusPublished - 1 Aug 2018
Event18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018 - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018

Conference

Conference18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018
CountryFinland
CityHelsinki
Period23.08.201824.08.2018

Keywords

  • Fixed-parameter tractability
  • NP-hard problem
  • Problem kernelization
  • Secluded solution
  • Shortest path

OECD FOS+WOS

  • 1.01 MATHEMATICS
  • 5.07 SOCIAL AND ECONOMIC GEOGRAPHY

State classification of scientific and technological information

  • 27.45 Combinatorial analysis. Graph theory

Fingerprint Dive into the research topics of 'Parameterized algorithms and data reduction for safe convoy routing'. Together they form a unique fingerprint.

Cite this