The complexity of routing with few collisions

DOI10.1007/978-3-662-55751-8_21MaRDI QIDQ1679978zbMATH OpenOpenAlexFDO

Authors Till Fluschnik, Marco Morik, Manuel Sorge

Publication date 22 November 2017

Full work available at URL https://arxiv.org/abs/1705.03673

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph $G$ with two distinct terminal vertices and two positive integers $p$ and $k$, the question is whether one can connect the terminals by at least $p$ routes (e.g. paths) such that at most $k$ edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if $k$ is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary $k$ and on directed graphs if $k$ is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs.

Recommendations

• The complexity of routing with collision avoidance
• The complexity of rerouting shortest paths
• The complexity of rerouting shortest paths
• Collision-free routing problem with restricted L-path
• Collision-free routing problem with restricted L-path
• On the computational complexity of continuous routing
• On the complexity of an optimal routing tree problem
• On the complexity of equal shortest path routing
• Complexity of pairwise shortest path routing in the grid
• The complexity of arc routing problems

Cited in

(6)

• The non-stop disjoint trajectories problem
• Problems on one way road networks
• On the approximability of time disjoint walks
• Collision-free routing problem with restricted L-path
• The complexity of routing with collision avoidance
• Collision-free routing problem with restricted L-path

This page was built for publication: The complexity of routing with few collisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679978)