The complexity of routing with collision avoidance

DOI10.1016/j.jcss.2019.01.001zbMath1421.68076OpenAlexW2911520398MaRDI QIDQ1741493

Marco Morik, Till Fluschnik, Manuel Sorge

Publication date: 3 May 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2019.01.001

zbMATH Keywords

NP-hardnessdynamic flowsmany-one reductionshared edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Related Items (3)

Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ The parameterized complexity of the minimum shared edges problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-dependent routing problems: a review
• The minimum vulnerability problem on specific graph classes
• Fundamentals of parameterized complexity
• Finding paths with minimum shared edges
• The minimum vulnerability problem
• Nash equilibria and the price of anarchy for flows over time
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The complexity of routing with few collisions
• The minimum shared edges problem on grid-like graphs
• Parametrized complexity theory.
• An Introduction to Network Flows over Time
• Traffic Networks and Flows over Time
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Reducibility among Combinatorial Problems
• The Parameterized Complexity of the Minimum Shared Edges Problem
• Temporal Network Optimization Subject to Connectivity Constraints
• Max flows in O(nm) time, or better
• Parameterized Algorithms
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks

This page was built for publication: The complexity of routing with collision avoidance