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

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)

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

• 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?)
• 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
• 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 NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Planar Hamiltonian Circuit Problem is NP-Complete
• 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 parameterized complexity of the minimum shared edges problem
• Time-dependent routing problems: a review
• Traffic Networks and Flows over Time

Cited in

(9)

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

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)