The complexity of routing with collision avoidance

DOI10.1016/J.JCSS.2019.01.001MaRDI QIDQ1741493zbMATH OpenOpenAlexFDO

Authors Till Fluschnik, Marco Morik, 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

dynamic flowsmany-one reductionNP-hardnessshared edges

Mathematics Subject Classification ID

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

Recommendations

• The complexity of routing with few collisions
• 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
• The complexity of arc routing problems
• On the complexity of an optimal routing tree problem
• On the complexity of multi-dimensional interval routing schemes
• scientific article; zbMATH DE number 1568938

Cites work

• A priority-based model of routing
• An introduction to network flows over time
• An introduction to temporal graphs: an algorithmic perspective
• Connectivity and inference problems for temporal networks
• Finding paths with minimum shared edges
• Fundamentals of parameterized complexity
• Graph theory
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Max flows in O(nm) time, or better
• Nash equilibria and the price of anarchy for flows over time
• Parameterized algorithms
• Parametrized complexity theory.
• Reducibility among combinatorial problems
• Temporal network optimization subject to connectivity constraints
• The complexity of routing with few collisions
• The minimum shared edges problem on grid-like graphs
• The minimum vulnerability problem
• The minimum vulnerability problem on specific graph classes
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The parameterized complexity of the minimum shared edges problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Time-dependent routing problems: a review
• Traffic Networks and Flows over Time

Cited in

(9)

• Collision-free routing problem with restricted L-path
• The complexity of routing with few collisions
• Collision-free routing problem with restricted L-path
• The parameterized complexity of the minimum shared edges problem
• Social network coordination and graph routing
• Problems on one way road networks
• On the approximability of time disjoint walks
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• Multistage \(s-t\) path: confronting similarity with dissimilarity

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

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